论文部分内容阅读
摘要：调度在车辆路径选择中常常扮演着重要的角色。本文描述了作者感兴趣的几个方向，包括路径问题中的速度优化问题，污染路径问题，并且作者提出了一些设想和展望。
关键词：车辆路径调度；时间窗口；速度优化
一、引言
本文的目的是描述几种时间和调度起着重要作用的路径问题。这种问题出现的次数很多。我们的目的不是要对所有可能的案例进行详尽的调查或分类，而是要描述近年来的有趣的问题。大多数车辆路径研究都是基于对传统车辆路径问题（VRP）的研究，该问题包括通过一组地理上分散的客户来确定车辆路线，且受到各种方面的限制。标准目标是距离（或成本）最小化。这个问题是由Dantzig和Ramser提出的，其研究从此演变成了一个丰富的研究领域。VRP中最常见的目标是距离最小化。当给路线持续时间施加上限时，通常将距离等同于旅行时间。但是，还有几种情况需要分开处理距离和时间。例如，在带时间窗的车辆路径问题（VRPTW）中，必须在给定的任意位置开始服务的时间间隔。如果车辆在时间窗口开始之前到达某个位置，则必须等待。在这种情况下，旅行的距离和路线的持续时间显然不相同。本文的其余部分安排如下。第2节至第3节分别讨论了如下话题：路径问题中的速度优化，污染路径问题。第5节中总结了本文的内容。
二、路径问题的速度优化
速度在路径和调度问题中很少出现作为决策变量。最近有关速度控制的研究主张减速作为降低成本和二氧化碳排放量的手段。这在当今的经济和环境背景下尤为重要。海运是减速可以产生可观节省的运输活动。为了说明这种影响，据估计，在450美元/吨的燃料价格下，全世界燃油消耗量减少1%，将使成本降低12亿美元以上，二氧化碳排放量减少1050万吨。由Norstad等人进行的计算研究已经表明，在合理的假设下，优化航线的速度可以减少多达14%的油耗。Fagerholt等人的论文提出了一些海上运输的速度控制模型和算法。简而言之，二氧化碳排放量与燃料消耗量成正比，在某些领域，二氧化碳排放量是一个凸增速度函数。由于成本凸性，在具有时间窗的路线上，这意味着如果在时间窗开始之前到达顶点，则高速航行是不理想的。航行速度最好慢一点，这样可以不必等待。本文认为一个固定的路线（v0，...，vn），其中在每个顶点vi的服务时间的开始处施加时间窗[ai， bi ]。总路径持续时间是给定的，即a0 = b0和an = bn。使用时间离散化，这个问题可以很容易地转化为有向无环图上的最短路径问题。在一项后续研究中，Hvattum等人提出了一个精确的O（n2） 算法来解决这个问题。只要旅行费用是速度的凸函数，它就是有效的，它适用于海运或地面运输。最初，该算法计算在时间an时到达vn所需的速度。然后确定路径（v0， . . . ， vn）上的最大时间窗违规。例如，假设这个最大违规相当于延迟到达顶点vi（ti>bi）。然后该算法以bi为到达时间在子路径（v0， . . . ， vi）上重新计算更高的速度，并以bi为出发时间在子路径（vi， . . . ， vn）上的较慢的速度。它在每个子路径上以同样的方式重复，直到不存在任何时间窗违规。在第3节，我们展示了如何使用速度优化作为减少货车卡车在或与运输中二氧化碳排放的工具。
三、污染路线问题
在大多数国家，货运占二氧化碳排放量的很大一部分。举例来说，据估计，在英国货运占运输部门排放量的21%，占排放总量的6%。Bektas和Laporte的论文是首先研究车辆路线中二氧化碳排放量的文章之一。根据Barth等人和Barth和Boriboonsomsin的文章，一个给定类型的车辆在平坦的路段上消耗的能量可以近似为公式
A和B是正的常数。这两个常数包括允许以能量单位（kWh）来衡量这两个术语的技术因素。假定速度超过约40公里/小时的特定阈值，因为通常低于这个速度驾驶商用车的效率会降低（参见Bektas和Laporte 2011）。行驶车辆产生的二氧化碳排放量或多或少与其消耗的能量成正比。Bektas和Laporte（2011）通过数学模型和各种示例的发展，阐述了车辆路线解决方案之间的各种相互作用。这些例子是以恒定的速度构建的，没有时间窗口。当在顶点到达时间施加时间窗口时，应用第2节中Hvattum等人的算法在给定路线上优化速度是很容易的。后一个例子清楚地说明了货运中速度和时间安排对二氧化碳排放量最小化的影响。设计数学模型是相对简单的，这种模型可以在时间窗存在的情况下，将一个或几个车辆的能耗降至最低，并具有目标函数（如（1））。但是，对于中等大小的实例，即使对于单个车辆，也无法准确解决这些模型。Demir等人最近设计并测试了自适应大邻域搜索启发式算法，该算法适用于大小符合实际的例子。在实践中，要使运营商在能耗最小化目标下设计路线可能是困难的，如果这样做比在成本最小化目标下获得的解决方案成本更高。通常情况下，通过缓慢驾驶来减少燃料消耗，这对驾驶时间和工资会产生不利影响。Bektas和Laporte通过一些计算实验表明，考虑到二氧化碳成本和燃料成本（甚至急剧增加），这一结论仍然成立，因为驾驶员成本往往占据整体解决方案成本的主导地位。例如Demir等人的文章，说明可以通过自适应大邻域搜索算法来最小化结合运营成本和CO2排放的全局函数。
四、总结
我们已经描述了几个路径问题，其中调度起着重要的作用。对于调度的需求通常是由时间窗的存在引起的，调度也与速度控制有关，这通常被用作减少二氧化碳排放的手段。我们提供了两个速度控制的例子，一个是远洋航运，另一个是车辆路线。最后，有一些问题需要几辆车的同步，例如我们所描述的两个弧路径问题。本文提供的例子反映了作者最近的研究兴趣。它们显然不代表调度在其中发挥重要作用的所有问题。潜在的应用数量非常大，我们希望这会吸引其他研究人员的兴趣。在组合路由和调度方面存在一些有前景的研究途径。第一个挑战是将交通堵塞和速度的可变性纳入最佳车辆路径和时间表的计算中。第二个有趣的研究课题是在供应链的不同层面上运行的车辆的同步，例如在转运和跨接操作的情况下。最后，例如关于拥塞的实时信息的可用性的增加，这就要求开发能够有效地处理在线信息和动态更新解决方案的算法。（作者单位：重庆交通大学 經济与管理学院）
作者简介：刘天鹤，1993年生，男，满族，研究生，研究方向：物流工程。
参考文献
[1]Baldacci R， Mingozzi A， & Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research， 2012（218）：1–6.
[2]Barth M， & Boriboonsomsin K. Energy and emissions impacts of a freeway-based dynamic ecodriving system[J]. Transportation Research. Part D， 2009（14）： 400–410.
[3]Bektas T，Laporte G.The pollution-routing problem. Transportation Research[J].Part B， 2011（45）：1232–1250.
[4]Demir E， Bektas T， & Laporte G. An adaptive large neighborhood search heuristic for thepollution-routing problem[J]. European Journal of Operational Research， 2012（223）：346–359.
[5]Drexl M.Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints[J]. Transportation Science，2012（46）：297–316.
关键词：车辆路径调度；时间窗口；速度优化
一、引言
本文的目的是描述几种时间和调度起着重要作用的路径问题。这种问题出现的次数很多。我们的目的不是要对所有可能的案例进行详尽的调查或分类，而是要描述近年来的有趣的问题。大多数车辆路径研究都是基于对传统车辆路径问题（VRP）的研究，该问题包括通过一组地理上分散的客户来确定车辆路线，且受到各种方面的限制。标准目标是距离（或成本）最小化。这个问题是由Dantzig和Ramser提出的，其研究从此演变成了一个丰富的研究领域。VRP中最常见的目标是距离最小化。当给路线持续时间施加上限时，通常将距离等同于旅行时间。但是，还有几种情况需要分开处理距离和时间。例如，在带时间窗的车辆路径问题（VRPTW）中，必须在给定的任意位置开始服务的时间间隔。如果车辆在时间窗口开始之前到达某个位置，则必须等待。在这种情况下，旅行的距离和路线的持续时间显然不相同。本文的其余部分安排如下。第2节至第3节分别讨论了如下话题：路径问题中的速度优化，污染路径问题。第5节中总结了本文的内容。
二、路径问题的速度优化
速度在路径和调度问题中很少出现作为决策变量。最近有关速度控制的研究主张减速作为降低成本和二氧化碳排放量的手段。这在当今的经济和环境背景下尤为重要。海运是减速可以产生可观节省的运输活动。为了说明这种影响，据估计，在450美元/吨的燃料价格下，全世界燃油消耗量减少1%，将使成本降低12亿美元以上，二氧化碳排放量减少1050万吨。由Norstad等人进行的计算研究已经表明，在合理的假设下，优化航线的速度可以减少多达14%的油耗。Fagerholt等人的论文提出了一些海上运输的速度控制模型和算法。简而言之，二氧化碳排放量与燃料消耗量成正比，在某些领域，二氧化碳排放量是一个凸增速度函数。由于成本凸性，在具有时间窗的路线上，这意味着如果在时间窗开始之前到达顶点，则高速航行是不理想的。航行速度最好慢一点，这样可以不必等待。本文认为一个固定的路线（v0，...，vn），其中在每个顶点vi的服务时间的开始处施加时间窗[ai， bi ]。总路径持续时间是给定的，即a0 = b0和an = bn。使用时间离散化，这个问题可以很容易地转化为有向无环图上的最短路径问题。在一项后续研究中，Hvattum等人提出了一个精确的O（n2） 算法来解决这个问题。只要旅行费用是速度的凸函数，它就是有效的，它适用于海运或地面运输。最初，该算法计算在时间an时到达vn所需的速度。然后确定路径（v0， . . . ， vn）上的最大时间窗违规。例如，假设这个最大违规相当于延迟到达顶点vi（ti>bi）。然后该算法以bi为到达时间在子路径（v0， . . . ， vi）上重新计算更高的速度，并以bi为出发时间在子路径（vi， . . . ， vn）上的较慢的速度。它在每个子路径上以同样的方式重复，直到不存在任何时间窗违规。在第3节，我们展示了如何使用速度优化作为减少货车卡车在或与运输中二氧化碳排放的工具。
三、污染路线问题
在大多数国家，货运占二氧化碳排放量的很大一部分。举例来说，据估计，在英国货运占运输部门排放量的21%，占排放总量的6%。Bektas和Laporte的论文是首先研究车辆路线中二氧化碳排放量的文章之一。根据Barth等人和Barth和Boriboonsomsin的文章，一个给定类型的车辆在平坦的路段上消耗的能量可以近似为公式
A和B是正的常数。这两个常数包括允许以能量单位（kWh）来衡量这两个术语的技术因素。假定速度超过约40公里/小时的特定阈值，因为通常低于这个速度驾驶商用车的效率会降低（参见Bektas和Laporte 2011）。行驶车辆产生的二氧化碳排放量或多或少与其消耗的能量成正比。Bektas和Laporte（2011）通过数学模型和各种示例的发展，阐述了车辆路线解决方案之间的各种相互作用。这些例子是以恒定的速度构建的，没有时间窗口。当在顶点到达时间施加时间窗口时，应用第2节中Hvattum等人的算法在给定路线上优化速度是很容易的。后一个例子清楚地说明了货运中速度和时间安排对二氧化碳排放量最小化的影响。设计数学模型是相对简单的，这种模型可以在时间窗存在的情况下，将一个或几个车辆的能耗降至最低，并具有目标函数（如（1））。但是，对于中等大小的实例，即使对于单个车辆，也无法准确解决这些模型。Demir等人最近设计并测试了自适应大邻域搜索启发式算法，该算法适用于大小符合实际的例子。在实践中，要使运营商在能耗最小化目标下设计路线可能是困难的，如果这样做比在成本最小化目标下获得的解决方案成本更高。通常情况下，通过缓慢驾驶来减少燃料消耗，这对驾驶时间和工资会产生不利影响。Bektas和Laporte通过一些计算实验表明，考虑到二氧化碳成本和燃料成本（甚至急剧增加），这一结论仍然成立，因为驾驶员成本往往占据整体解决方案成本的主导地位。例如Demir等人的文章，说明可以通过自适应大邻域搜索算法来最小化结合运营成本和CO2排放的全局函数。
四、总结
我们已经描述了几个路径问题，其中调度起着重要的作用。对于调度的需求通常是由时间窗的存在引起的，调度也与速度控制有关，这通常被用作减少二氧化碳排放的手段。我们提供了两个速度控制的例子，一个是远洋航运，另一个是车辆路线。最后，有一些问题需要几辆车的同步，例如我们所描述的两个弧路径问题。本文提供的例子反映了作者最近的研究兴趣。它们显然不代表调度在其中发挥重要作用的所有问题。潜在的应用数量非常大，我们希望这会吸引其他研究人员的兴趣。在组合路由和调度方面存在一些有前景的研究途径。第一个挑战是将交通堵塞和速度的可变性纳入最佳车辆路径和时间表的计算中。第二个有趣的研究课题是在供应链的不同层面上运行的车辆的同步，例如在转运和跨接操作的情况下。最后，例如关于拥塞的实时信息的可用性的增加，这就要求开发能够有效地处理在线信息和动态更新解决方案的算法。（作者单位：重庆交通大学 經济与管理学院）
作者简介：刘天鹤，1993年生，男，满族，研究生，研究方向：物流工程。
参考文献
[1]Baldacci R， Mingozzi A， & Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research， 2012（218）：1–6.
[2]Barth M， & Boriboonsomsin K. Energy and emissions impacts of a freeway-based dynamic ecodriving system[J]. Transportation Research. Part D， 2009（14）： 400–410.
[3]Bektas T，Laporte G.The pollution-routing problem. Transportation Research[J].Part B， 2011（45）：1232–1250.
[4]Demir E， Bektas T， & Laporte G. An adaptive large neighborhood search heuristic for thepollution-routing problem[J]. European Journal of Operational Research， 2012（223）：346–359.
[5]Drexl M.Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints[J]. Transportation Science，2012（46）：297–316.