多车场满载协同运输问题模型与算法  

Full-Load Multi-Depot Collaborative Transportation Problem:Models and Algorithms

作　　者：刘冉[1] 江志斌[1] 陈峰[1] 刘黎明[2] 刘树军[1] 刘天堂[1] 

机构地区：[1]上海交通大学机械与动力工程学院,上海200240 [2]香港理工大学物流学系,中国香港

出　　处：《上海交通大学学报》2009年第3期455-459,共5页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金国际(地区)合作交流项目(70831160527);国家自然科学基金资助项目(70872077,70771063)

摘　　要：多车场满载条件下的协同运输问题属于NP-hard难题.在分析此问题和MDPDP以及MDARP区别的基础上,考虑车辆最大行驶距离的约束条件,建立了此类问题的数学模型.为了有效求解实际大规模的多车场满载协同运输问题,设计了基于贪婪算法的两阶段启发式算法.该算法第1阶段形成完全覆盖运输任务弧的回路集,第2阶段组合连接回路,构造形成起止于车场的闭通路.最后,利用局域搜索对求得的解改进以得到最终解.实验表明,算法是可行和有效的.Collaborative transportation is an emerging kind of transportation mode, which represents one of major trends of transportation. Multi-depot, full-load collaborative transportation problem is an NP-hard problem. In terms of the similarity and difference among such problem, MDPDP and MDARP, the mathematical model was established. In order to solve the practical large scale problem, a two-phase heuristic algorithm based on greedy algorithm was proposed. In the first phase of the proposed algorithm, the cycles covering the transportation lanes are created. In the second phase the roads composed of cycles are formed, and each of the roads passes by one of the depots. Finally, a local search approach was proposed to improve the initial solution. The simulative computational results demonstrate that the proposed algorithm is feasible and effective.

关 键 词：协同运输 多车场 满载 两阶段启发式算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]