带时间窗的同时集散货物路线问题研究  

The Study on Vehicle Routing Problem of Simultaneous Deliveries and Pickups with Time Windows

作　　者：李建[1] 张永[2] 

机构地区：[1]南京农业大学工学院,江苏南京210031 [2]东南大学交通学院,江苏南京210096

出　　处：《信息与控制》2009年第6期752-758,共7页Information and Control

基　　金：国家自然科学基金资助项目(70772059);江苏省农机局基金资助项目(GXZ08002)

摘　　要：研究了业务繁忙环境下带时间窗的同时集散货物路线问题.以车辆数、运输距离和完成运输任务的总时间最小为目标建立了多目标模型,提出用基于路线集合划分的分解迭代算法求解该问题.该算法首先用两种策略将问题的解分解为几个子集合,用记录更新法分别求解每个子集合,将子集合求得的最好路线反馈回来形成新的当前解,再分解迭代,逐渐改善解的质量.最后数据实验表明该算法能有效解决带时间窗的单向车辆路线问题和集散一体化的双向车辆路线问题.Vehicle routing problem of simultaneous deliveries and pickups with time windows （VRPSDPTW） is studied under the circumstances of rapidly increasing customers. A multiobjective model is formulated with the minimum number of the vehicles, traveling distances and the sum of traveling times, serving times and waiting times. Decomposition and iteration algorithm based on route set partition is proposed： a solution is divided into several subsets by two strategies, which are respectively solved by record-to-record travel algorithm. Then the best solutions of the subsets are merged to form a new current solution. This process is repeated so that the solution can be gradually improved. Computational results show that this algorithm is effective to resolve vehicle routing problem with time windows of both one-way deliveries and simultaneous deliveries and pickups.

关 键 词：同时集散货物路线问题 时间窗 多目标 分解迭代法 记录更新法 

分 类 号：U116.2[交通运输工程]