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

Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window

作　　者：祁文祥[1] 陆志强[1] 孙小明[1] 

机构地区：[1]上海交通大学机械与动力工程学院,上海200240

出　　处：《交通运输工程学报》2010年第2期99-103,109,共6页Journal of Traffic and Transportation Engineering

基　　金：国家自然科学基金项目(70771065);上海市浦江人才计划项目(07PJ14052)

摘　　要：研究了物流配送中多车运输的集货与送货车辆路径规划问题,以增加时间惩罚费用的方式插入软时间窗约束,将租车费用、货车运输费用和时间惩罚费用三者之和最小作为优化目标,建立数学模型。采用启发式节约算法求解该模型,考虑时间惩罚费用和运输费用,比较每一配送节点上直接送货和间接送货的节约费用关系,求出最优配送路径。试验结果表明:当配送次数达到50次时,货车平均装载率仍能达到80%以上,该节约算法能减少货车空程行驶和租车次数,优化了全局费用。Multi-vehicle routing problem with pickups and deliveries was studied,and soft time window constraint was considered by adding time punishment cost.The mathematical model was built,and its optimized object was the minimum of combination with vehicle rent cost,transportation cost and time punishment cost,and the model was solved by using heuristic saving algorithm.Time punishment cost and transpiration cost were calculated respectively,and the relation between direct and indirect deliveries was compared to obtain best routes.Test result indicates that when 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 without loadage and rent times,and optimize total cost.2 tabs,4 figs,11 refs.

关 键 词：多车辆路径问题 集货与送货 启发式节约算法 软时间窗 

分 类 号：U492.3[交通运输工程—交通运输规划与管理]