An exact solution approach for vehicle routing and scheduling problems with soft time windows
An exact solution approach for vehicle routing and scheduling problems with soft time windows
复制标题
DOI：
10.1016/j.tre.2009.04.007
复制
发表时间：
2009-11
影响因子：
10.6
通讯作者：
A. Qureshi;E. Taniguchi;Tadashi Yamada
中科院分区：
文献类型：
--
作者：
A. Qureshi;E. Taniguchi;Tadashi Yamada
针对带半软时间窗的车辆路径调度问题，提出了一种基于列生成的精确优化方法。在Dantzig-Wolfe分解方法的基础上，将具有资源约束和迟到惩罚的初等最短路径问题作为子问题求解。在所罗门基准算例和东京路网算例上，对VRPSSTW和硬时间窗变量的精确解进行了比较。研究发现，VRPSSTW解决方案减少了路线，从而降低了总成本，并且迟到惩罚只占总成本的一小部分。
A new column generation based exact optimization approach for the vehicle routing and scheduling problem with semi soft time windows (VRPSSTW) is presented. Elementary shortest path problem with resource constraints and late arrival penalties is solved as a subproblem, which rises from the Dantzig–Wolfe decomposition method. Exact solutions of VRPSSTW and hard time windows variant are compared on Solomon’s benchmark instances as well as on an instance based on Tokyo road network. It was found that the VRPSSTW solution results in fewer routes thus overall costs are reduced and late arrival penalties contribute only a small fraction to total cost.