The Synchronized Vehicle Dispatching Problem
The Synchronized Vehicle Dispatching Problem
复制标题
同步车辆调度问题
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
G. Pesant
中科院分区：
文献类型：
--
作者：
Louis;M. Gendreau;G. Pesant
同步车辆调度问题（SVDP）是一个在现实世界中出现的交通问题。一个很好地说明了这个问题的特殊版本是“叫车”问题，在这个问题中，一些残疾人需要帮助，以便为交通做准备。在这种情况下，一个特别的团队会在车辆开始前几分钟被派往特殊客户的住所，以确保安全有效地进行转移。这种帮助可以从冬季穿衣到提供轮椅帮助，通常不是在任何时候或所有客户都需要。这意味着特别援助小组的时间表需要与舰队其余部分的时间表同步。据我们所知，这个问题还没有在文献中提出，但是车辆调度问题有许多变体，涵盖了许多实际应用。Gendreau and Potvin bb1， Qiu and Hsu bb2和Psaraftis bb1发表了详细的调查报告，描述了不同的问题和解决方法。最有效的算法是用局部搜索技术（比如实例的禁忌搜索）来解决这个问题。Ichoua[3]后来引入了一种分类法来进一步对这类问题进行分类。同步约束使得使用传统的局部搜索方法很难解决这个问题。例如，如果一个特殊客户的插入延迟了一辆特殊车辆的路线，那么与该路线相关的所有常规访问也必须延迟，而与为他们提供服务的车辆无关。但是，推迟一辆常规车辆也意味着推迟与其他特殊客户相关的访问等等。如此高的互连数量意味着要插入一个客户，可能必须重新计算已插入的每个客户的访问时间。因此，约束编程似乎非常适合这类问题，因为它不仅提供了一种表达同步约束的简单方法，而且通过将访问时间表示为域变量并仅在需要时传播同步约束，它允许有效地实现这些约束。
The synchronized Vehicle Dispatching Problem (SVDP) is a transportation problem that arises in many real world situations. One that illustrates well this problem is special version of the Dial-a-Ride problem, in which some disabled persons require assistance in order to prepare for transportation. In this case, a special team is sent to the residence of the special customer a few minutes before the vehicle to insure that the transfer is made safely and efficiently. The help can vary from dressing for winter conditions to providing wheelchair assistance and is not usually required at all times or by all customers. This means the schedule of the special assistance teams needs to be synchronized with the schedules of the rest of the fleet. To our knowledge this problem has not yet been presented in the literature, however there are many variants of the Vehicle Dispatching Problem covering many real life applications. Gendreau and Potvin [1], Qiu and Hsu [6] and Psaraftis [5] have published detailed surveys describing the different problems and solution approaches. Most efficient algorithms address this problem with local search techniques (like Tabu search for instances). Ichoua [3] has later introduced a taxonomy to further categorize the problems of this class. The synchronization constraints make this problem quite hard to solve using traditional local search methods. For instance, if the insertion of a special customer delays the route of a special vehicle then all regular visits associated with that route must also be delayed, independently of the vehicle that serviced them. But delaying a regular vehicle means delaying also the visits associated with other special customers and so on. This high number of interconnections means that to insert one customer one might have to recompute the visit time of every customer already inserted. Constraint Programming thus seems well suited for this kind of problem since it not only provides an easy way to express the synchronization constraints but, by representing visit times as domain variables and by propagating the synchronization constraints only when needed, it allows an efficient implementation of those constraints.