MK_带软时间窗的集货与送货多车辆路径问题节约算法.pdfVIP

第10 卷 第2 期 交 通 运 输 工 程 学 报 Vol10 No2 2010 年4 月 Journal of Traffic and T ransportation Engineering Apr. 2010 : 1 711 37( 2010) 祁文祥, 陆志强, 孙小明 ( , 200240) : 研究了物流配送中多 运输的集货与送货 辆路径规划问题, 以增加时间惩罚费用的方式插 入软时间窗约束, 将租 费用货 运输费用和时间惩罚费用三者之和最小作为优化目标, 建立数学 模型采用启发式节约算法求解该模型, 考虑时间惩罚费用和运输费用, 比较每一配送节点上直接送 货和间接送货的节约费用关系, 求出最优配送路径试验结果表明: 当配送次数达到50 次时, 货 平 均装载率仍能达到80%以上, 该节约算法能减少货 空程行驶和租 次数, 优化了全局费用 : 多 辆路径问题; 集货与送货; 启发式节约算法; 软时间窗 : U 492. 3 : A Saving algorithm of multivehicle routing problem with pickupdelivery andsoft time window QI Wenxiang, LU Zhiqiang, SU N Xiaoming ( School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240, China) Abstract: Multivehicle routing problem w ith pickups and deliveries w as studied, and soft time w indow constraint w as considered by adding time punishment cost. The mathematical model w as built, and its optimized object w as the minimum of combination w ith vehicle rent cost, transportation cost and time punishment cost, and the model w as solved by using heuristic saving algorithm. T ime punishment cost and transpiration cost w ere calculated respectively , and the relation betw een direct and indirect deliveries w as compared to obtain best routes. T est result indicates that w hen the times of pickups and deliveries reach 50, the average loading rate of freight car still achieves above 80%, so the heuristic saving algorithm can reduce the distance w ithout loadage and rent times, and optimize total cost. 2 tabs, 4 figs, 11 refs. Key words: multivehicle routing problem; pickup and delivery; heuristic saving algorithm; soft time w indow Author resumes: QI W enxiang( 1984) , male, graduate student, + 8 213420 782, sjtuqwx@ gmail. com;