Waiting Strategies for the Dynamic Vehicle Routing Problem with Time Windows
Wong Ka Io
|關鍵字:||等待策略;動態;即時需求;時窗限制下的車輛路線問題;Waiting Strategies;Dynamic;Real-time request;Vehicle Routing Problem withTimeWindows|
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.
|Appears in Collections:||Research Plans|
Files in This Item: