Abstract: This paper investigates the dispatching and routing problem of heterogonous and multi-compartment vehicles in the distribution of product oil, which has to simultaneously consider the assignment of heterogonous vehicles, the loading policies of multi-compartment vehicles and routing decisions. A dispatching and routing model of heterogonous and multi-compartment vehicles is developed with the objective of minimizing total operating cost which consists of vehicle dispatching cost and fuel cost. To reduce the complexity of model solution, based on C-W algorithm, a vehicle loading policy called “splitting demandcombining load” is presented, and the optimized routing scheme of vehicles is obtained through two parallel neighborhood searching operators of Relocate and Exchange. Finally, the efficiency of the model and algorithm proposed in this paper for solving large-scale dispatching and routing problem of heterogonous and multi-compartment vehicles in the distribution of product oil is verified by computational results. Through further computational experiment, the following rules are revealed: 1)the multi-compartment vehicle is superior to the single compartment vehicle in operating costs; 2)the vehicle with large capacity is suitable for long distance distribution, while the vehicle with small capacity is suitable for short distance distribution; and 3)the heterogonous vehicle fleet is superior to the single type vehicle fleet in operating costs in practice of the distribution of product oil, which provide a reference for the vehicle configuration of product oil distribution company.

Key words: product oil distribution, multi-compartment vehicle routing problem, optimization method in operations research, vehicle dispatching problem

摘要： 针对成品油配送中多车型、多车舱的车辆优化调度难题,综合考虑多车型车辆指派、多车舱车辆装载及路径安排等决策,以派车成本与油耗成本之和的总成本最小为目标,建立了多车型多车舱的车辆优化调度模型。为降低模型求解的复杂性,本文提出一种基于C-W节约算法的“需求拆分→合并装载”的车辆装载策略,并综合利用Relocate和Exchange算子进行并行邻域搜索改进,获得优化的成品油配送方案。最后,通过算例验证了本文提出的模型与算法用于求解大规模成品油配送问题的有效性。并通过数据实验揭示了以下规律:1)多车舱车辆相对于单车舱车辆在运营成本上具有优越性;2)大型车辆适合远距离配送,小型车辆适合近距离配送;3)多车型车辆混合配送相对于单车型车辆配送在运营成本上具有优越性。这些规律可为成品油配送公司的车辆配置提供决策参考。

关键词: 成品油配送, 多车舱车辆路径问题(MCVRP), 运筹学优化方法, 车辆指派问题