带时间窗的多车型多费用车辆路径问题的模型和算法

Model and Heuristic Algorithim for the Multi-type Vehicles Routing Problem with Multiple Costs and Time Windows Limits

创新性地考虑了多车型车辆路径问题中不同车型具有不同的边际费用和行驶费用的问题,并同时考虑车型与任务的相容性,对带时间窗约束的多车型多费用非满载车辆路径问题,以最小化总费用为目标建立了数学模型.由于该模型的NP-hard性质,基于高费用车型的边际费用和单位行驶费用比低费用车型的相应费用都要高以及低费用车型的边际费用远大于高费用车型的单位行驶费用的思想,对该模型设计了一个启发式算法.

In this paper, using multiple-type vehicles to collect or deliver cargos with time windows and non-full loads vehicle routing problem is innovatively considered that different type vehicles have different marginal costs and travel eosts. The eompatibility eonstraints among vehiele types and eargos are also eonsidered. Mathematieal model aims at minimize the total eost for the problem is then presented. Beeanse of the NP-hard attribute of the model, a new heuristic is designed based on the idea that the marginal cost and the unit travel cost of high-cost vehicle are higher than those of low-cost vehicle and the marginal cost of low-cost vehicle is still much higher than the unit travel cost of high-cost vehicle.