摘要
研究带时间窗口的物流配送车辆路径问题(VRPTW),主要考虑车辆容量、时间窗口、最大距离等约束,且完成配送所需的车辆数目不确定,要求在车辆数目最少的条件下再使总的行驶路径最短.提出了该问题的混合整数规划模型,运用改进差分进化算法求解该问题.算法采用序数编码,设计辅助算子解决变异问题,差分进化的交叉率随进化代数自动更新.应用MATLAB语言编程进行仿真计算,得到了最优解,结果表明该算法是求解带时间窗的车辆路径问题的一种有效方法。
The logistics distribution vehicle routing problem with time windows （VRPTW） was considered, which contains the vehicle capacity restriction, time windows restriction and the longest distance restriction, and the number of vehicle is uncertain, the solution must ensure the number of vehicle is least at first, and the total distance is the shortest. A mixed integer programming model was proposed, and an improved differential evolution algorithm was presented for this problem. In the algorithm, the novel ordinal number coding was firstly adopted to construct the chromosome, and then an auxiliary operator was designed to solve the mutation problem, and the probability of crossover was updated with iteration number. The advantage of the proposed algorithm was proved by the simulation based on MATLAB language. The computational results demonstrate that the improved differential evolution algorithm can solve the vehicle routing problem with time window effectively.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2009年第8期2420-2423,共4页
Journal of System Simulation
基金
国家科技支撑计划项目(2006BAJ07B03
2008FJ1006)
关键词
物流配送
车辆路径问题
差分进化算法
时间窗口
混合整数规划
logistics distribution
vehicle routing problem
differential evolution algorithm
time windows
mixed integer programming
