A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution
A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution
复制标题
DOI：
10.1007/s13676-012-0004-y
复制
发表时间：
2012-06-01
影响因子：
2.4
通讯作者：
Zografos, Konstantinos G.
中科院分区：
文献类型：
--
作者：
Androutsopoulos, Konstantinos N.;Zografos, Konstantinos G.
规划危险品配送路线，以服务于一组给定的订单在指定的时间窗口是一个问题，经常出现在城市物流环境，其特点是动态的旅行时间。危险品配送问题涉及到确定配送顺序和分配给每辆卡车的相应路径。将危险品配送问题转化为一个带时间窗的双目标时间相关车辆路径问题。本文提出了一个多目标的整数网络流模型的数学公式的问题。应用加权和法将双目标车辆路径与调度问题分解为一系列单目标问题，目标函数由所考虑的准则的加权和表示。一个路线建设的启发式算法，提出了解决每个组成的单目标问题，在未完成的路线的前面部分迭代插入停止。一个标签设置算法集成在启发式算法中，用于解决多个中间站插入后产生的路径中的任何停止时间依赖的最短路径问题。所提出的求解方法已应用于一组可解的测试问题，以评估启发式解的准确性。结果表明，启发式解决方案从实际的非支配解决方案的偏差是可以容忍的。此外，该算法被应用到一组类似于现实生活中的问题的情况下，测试问题。解决这类测试问题所需的平均计算时间并不令人望而却步。
Planning hazardous materials distribution routes for servicing a given set of orders within specified time windows is a problem frequently surfacing in a city logistics environment which is characterized by dynamic travel times. The hazardous materials distribution probleminvolves the determination of the sequence of deliveries and the corresponding paths assigned to each truck. This paper presents the formulation of the hazardous materials distribution problem as a bi-objective time-dependent vehicle routing problem with time windows. The paper presents the mathematical formulation of the problem as an integer network flow model with multiple objectives. The weighted-summethod is applied decomposing the bi-objective vehicle routing and scheduling problem to a series of single-objective instances of the problem, where the objective function is expressed by the weighted sum of the criteria under consideration. A route-building heuristic algorithm is presented for addressing each of the constituent single-objective problems, where stops are inserted iteratively in the front part of the unfinished route. A label-setting algorithm is integrated in the heuristic algorithm for solving the time-dependent shortest path problem with multiple intermediate stops arising after the insertion of any stop in the route. The proposed solution approach has been applied to a set of solvable test problems to assess the accuracy of the heuristic solutions. The results indicate a tolerable deviation of the heuristic solutions from the actual non-dominated solutions. In addition, the proposed algorithm was applied to a set of test problems resembling real-life problem cases. The average computational time needed for solving this type of test problems is not prohibitive.