系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
Systems Engineering—Theory & Practice
2008年
2期
143~147
,共null页
王素欣 高利 崔小光 陈雪梅
王素訢 高利 崔小光 陳雪梅
왕소흔 고리 최소광 진설매
多集散点 车辆路径问题 蚁群算法 禁忌表
多集散點 車輛路徑問題 蟻群算法 禁忌錶
다집산점 차량로경문제 의군산법 금기표
multi-depots; vehicle routing problem; ant colony optimization; tabu table
为使多集散点车辆路径问题结果全局最优,以订单为基准建立货运车辆路径问题模型.以订单为基准建立蚁群算法的二维禁忌数组,确定相邻两个集散点相同时的蚂蚁状态转移规则,使蚁群在满足车辆约束条件下,按禁忌表对所有订单搜索.此模型和算法实现了所有车辆对所有订单进行路径搜索,易于全局最优.实例求解结果表明模型及算法的有效性.
為使多集散點車輛路徑問題結果全跼最優,以訂單為基準建立貨運車輛路徑問題模型.以訂單為基準建立蟻群算法的二維禁忌數組,確定相鄰兩箇集散點相同時的螞蟻狀態轉移規則,使蟻群在滿足車輛約束條件下,按禁忌錶對所有訂單搜索.此模型和算法實現瞭所有車輛對所有訂單進行路徑搜索,易于全跼最優.實例求解結果錶明模型及算法的有效性.
위사다집산점차량로경문제결과전국최우,이정단위기준건립화운차량로경문제모형.이정단위기준건립의군산법적이유금기수조,학정상린량개집산점상동시적마의상태전이규칙,사의군재만족차량약속조건하,안금기표대소유정단수색.차모형화산법실현료소유차량대소유정단진행로경수색,역우전국최우.실례구해결과표명모형급산법적유효성.
In order to get the global solution in multi-depots vehicle routing problem (VRP), VRP model based on detail order information was established. A two dimension tabu table based on orders was established for ant colony optimization algorithm, and state transfer rules were established when the two adjacent nodes were same. Then all the vehicle routs were searched by ants that satisfied the vehicle constrain according to ants tabu table. It is easy to get the global solution for model and algorithm implement the routs search of all vehicles to all orders. The illustration result shows that model and algorithm are effective for multi-depots vehicle routing problem.