Abstract: 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 costs. The compatibility constraints among vehicle types and cargos are also considered. Mathematical model aims at minimize the total cost for the problem is then presented. Because 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.

Key words: vehicle routing problem;multiple-type vehicles;multiple costs;compatibility constraints, time windows;ranking;heuristic

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

关键词: 车辆路径问题, 多车型, 多费用, 相容性, 时间窗, 排序, 启发式算法