- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
混合粒子群与细菌觅食演算法解决容量限制车辆途程问题
混合粒子群與細菌覓食演算法解決容量限制車輛途程問題
高有成
大同大學資訊經營所
ykao@.tw
張怡凡
大同大學資訊經營所
rexmax0912@
摘要
為滿足企業的物流配送需求,車輛路線安排與規劃就越顯重要,車輛途程問題的目
標是希望 找出各車的容積都能符合且行車總距離又達到最短,以節省成本並提高效率 。
車輛途程是一種組合最佳化問題, 其求解難度更是屬於NP-Hard ,當問題規模越來越大
時就很難找到確切解,所以希望透過巨集啟發式演算法在有效率的時間內找到品質精確
的近似最佳解 。本研究利用粒子群演算法的全域有哪些信誉好的足球投注网站能力和細菌演算覓食法的區域搜尋
能力相結合來期望產生不錯的解的品質和程式執行效率。實驗結果顯示,本研究所提出
之演算法能夠有效解決容量限制下之車輛途程問題。
關鍵詞 :車輛途程問題、粒子群最佳化演算法、細菌覓食演算法
混合粒子群與細菌覓食演算法解 決容量限制車輛途程問題
壹、簡介
組合最佳化問題的種類繁多常見的包含車輛途程問題 、單元形成問題、投資組合最
佳化問題 等等。車輛 途程問題(Vehicle Routing Problem)是眾多 排列組合最佳化問題中的
一門,在運輸領域上是相當實用且重要的一個客題。於 1959 年由Dantzig and Ramser[6]
所提出後 ,目前已發展出多種應用形式。 2008 年Jozefowiez 等人[7]針對問題定義、目
標、演算法作了詳細的分類與比較 。而最典型的車輛途程問題就是容量限制下車輛 途程
問題 (Capacitated Vehicle Routing Problem ,CVRP) 。其中容量限制車輛 途程問題的目標
是要在容量符合的情況下總里程數要最小並且要拜訪完所有的客戶,限制條件為每輛車
均須自場站出發並返回場站、每位客戶恰好由某輛車服務一次、每輛車的最大裝載容量
不得超過最大限制容量 。解容量限制下車輛途程問題的演算法通常會遇到一些困難:演
化後的解違反限制式、陷入區域最佳解、收斂速度,計算時間過長 等等。
由於車輛 途程問題的解題難度屬於 NP-hard ,如果使用精確求解 演算法 (exact
algorithms)很難在有效率的時間內找到一組近似最佳解,而巨集啟發式演算法
(meta-heuristic algorithms)的特徵就是演化的解會逐漸朝向更佳的方向前進,且有一定能
力有哪些信誉好的足球投注网站其他未探索過的區域,避免最終陷入過早收斂又跳不出區域最佳解的情況。巨集
啟發式 演算法包括 基因演算法(Genetic Algorithm ,GA) 、模擬退火法(Simulated
Annealing ,SA )、禁忌搜尋法(Tabu Search ,TS) 、蟻群最佳化演算法 (Ants Colony
Optimization ,ACO) 、粒子群最佳化演算法(Particle Swarm Optimization ,PSO) 、細菌覓
食最佳化 (Bacterial Foraging Optimization ,BFO) 等等。
其中如果用解的數量來進行區分,則可以將上述演算法區分為單一解和群體解兩
類,模擬退火法和禁忌搜尋法屬於單一解;基因演算法、蟻群最佳化演算法、粒子群最
佳化演算法 、細菌覓食最佳化、蜜蜂最佳化演算法屬於群體解而這些最佳化演算法也被
稱為群體智慧演算法 。
1995年Alex 學者[15]使用 SA並結合區域搜尋將途程分為兩途程間交換顧客成員或
是單途程的交換顧客順序 ,以此做較大幅度的變動希望解決過早陷入區域最佳的機率。
2006年R. Tavakkoli-Moghaddam 等學者[17]將SA和最近鄰居法、 1-opt 、2-opt結合都是
為了盡量增加解的有哪些信誉好的足球投注网站範圍。
1998年P.
您可能关注的文档
- 河北精品课程评价指标2007-防灾科技学院教务处.DOC
- 河北2014年中小学校及幼儿园教师全员远程培训-厦门-厦门.PPT
- 泉州幼儿师范高等专科学校-中国高职高专教育网.DOC
- 沿程水头损失是否相等.PPT
- 泉州铁路与经济发展.PPT
- 泡沫材料屈服应力-塑性应变数据FoamHardeningHydrostaticyield.PPT
- 泡绵发泡反应.PPT
- 注音并解释词语贻误颟顸渊薮憬悟情愫驾驭滞涩yímānhānsǒujǐng.PPT
- 泵和压缩机的高级转速控制Vorecon双变矩器调速之星-cloudfrontnet.PDF
- 洗碗机-兴隆大家庭.DOC
- 2025年广东金融学院单招职业倾向性考试必刷测试卷附答案.docx
- 2025年广元中核职业技术学院单招职业适应性考试必刷测试卷附答案.docx
- 2025年广东食品药品职业学院单招职业适应性测试题库必威体育精装版.docx
- 2025年广东食品药品职业学院单招职业适应性测试题库附答案.docx
- 2025年广州体育职业技术学院单招综合素质考试必刷测试卷附答案.docx
- 2025年广东金融学院单招综合素质考试题库附答案.docx
- 2025年FRM金融风险管理师考试金融风险管理师面试技巧提升试卷.docx
- 2025年广元中核职业技术学院单招职业适应性测试题库附答案.docx
- 2025年广东金融学院单招职业技能测试必刷测试卷必威体育精装版.docx
- 2025年广东食品药品职业学院单招职业适应性考试题库必威体育精装版.docx
最近下载
- 中药炮制实训指导.doc.doc
- 《基础会计(原初级会计学)(第12版)》课件 秦玉玺 第7-13章 会计账簿-会计管理相关工作规范.pptx
- 新能源汽车电池回收的供应链协同优化策略研究.pdf VIP
- 新能源汽车电池项目商业计划书.docx VIP
- 2025年一建《建筑工程管理与实务》案例300问.pdf VIP
- 江苏省泰州市兴化市2023-2024学年八年级下学期期中地理试题(原卷版).pdf VIP
- 护士岗位职责试题(附答案).docx VIP
- 江苏省泰州市兴化市2023-2024学年八年级下学期期中考试英语试题.docx VIP
- 教资试题电子版(14套).pdf
- 2024《中国商业银行绿色金融实践研究:以中国工商银行为例》9400字.doc
文档评论(0)