時窗限制下的動態車輛路線問題之等待策略

Abstract

時窗限制下的車輛路線問題已經有廣泛的研究，問題主要為規劃車輛路線以滿足所有 含時間窗限制的需求點，而目標一般為最少車輛數與最少總行走距離。目前的相關研 究重於靜態問題之求解，而近年由於電子導航及通訊科技發展越趨成熟，實時車輛指 派的容易度增加，得使動態需求的加入變得可行。本研究之目的是要發展一套有效之 等待策略去求解動態的時窗限制下的車輛路線問題。等待策略意即把車輛安排在適當 的地點等待，使增加可以接受即時需求的可能性。透過幾何機率的方法，預期可以找 到一個在一般動態車輛路線問題皆可使用的最佳等待策略。

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and classic problem in Logistic management and Operations research. The problem is to determine a set of routes for a fleet of vehicles visiting a number of known customers associated with time windows, and the objective is to minimize the number of vehicles required and the total travel time. It is a combinatorial optimization problem and has been studied in numerous papers. The dynamic vehicle routing problem with real-time requests has been becoming important in the logistic industry with the latest advancements in Information and Communication Technologies (ICT) and Geographic Information Systems (GIS). It is now possible to develop efficient dispatching systems by using real-time, high quality and reliable positional information. While known requests with specified time windows are preplanned, new customer requests are to be considered for possible insertion. The objective of this study is to develop an optimal strategy trying to maximize the probability of inserting additional real-time requests in the existing routes, and it is analogues to the goal of minimizing the number of required vehicles as well as total travel distances. This can be achieved by holding a vehicle at appropriate locations so as to exploit a larger region of service being able to reach at a limited slack time. This idea can be further elaborated as to determine 1) the optimal length of waiting time, 2) the optimal location to wait and 3) the optimal speed of the vehicle. Once a route for VRPTW is computed, by using the Drive First and Wait First strategies, it is possible to determine the lower bound and upper bound of waiting along the route. The probability of a vehicle serving a real-time demand can then be calculated by the method of geometric probability. It is expected that we can determine an analytical solution for the simple case of single vehicle, and heuristic rules can be developed for a general dynamic VRP problems.