范厚明,刘 浩,刘鹏程,任晓雪

(大连海事大学交通运输工程学院,辽宁大连 116026)

1 引言

车辆路径问题自1959年被提出以来[1],引起了众多学者对其研究,并通过将不同约束加入到经典车辆路径问题(vehicle routing problem,VRP)问题中,使其越来越贴近于实际,逐步衍生出同时配集货车车辆路径问题(vehicle routing problem with simultaneous delivery and pickup,VRPSDP)、异型车辆路径问题(heterogeneous fleet vehicle routing problem,HFVRP)及模糊需求车辆路径问题(vehicle routing problem with fuzzy demand,VRPFD)等.本文研究的集货需求模糊的异型车同时配集货车辆路径问题(heterogeneous fleet vehicle routing problem with simultaneous deterministic delivery and fuzzy pickup,HFVRPSDDFP)是综合考虑了VRPSDP,HFVRP以及VRPFD问题特点而形成的科学问题.现实中,如饮料供应商的配送中心使用不同型号的配送车辆,依据客户需求订单对客户进行配送服务的同时回收可再使用容器(空瓶)、过期饮品,其中配货需求依据订单是确定的,回收空瓶及过期饮品(集货需求)往往是不确定的,具有模糊特征;同样,玻璃厂依据订单配送玻璃的同时回收碎玻璃;医疗药品配送的同时回收过期药品等,都是物流生产过程需要解决的问题.因此针对HFVRPSDDFP展开研究具有理论和现实意义.

有关VRPSDP,HFVRP和VRPFD问题近年来已经成为VRP扩展问题研究的热点.针对VRPSDP的研究,刘玲等[2]对需求可拆分的VRPSDP问题进行研究,设计变邻域搜索算法对问题进行求解.Zhu等[3]对带有随机需求的VRPSDP问题进行研究,设计自适应大邻域搜索算法对问题进行求解.王超等[4]研究了带有时间窗的VRPSDP问题,设计离散布谷鸟算法对问题进行求解.Shi等[5]研究了带有随机旅行和服务时间的VRPSDP问题,并采用Gurobi、混合遗传算法、模拟退火算法、蝙蝠算法和萤火……