Title: 時窗限制下的動態車輛路線問題之等待策略
Waiting Strategies for the Dynamic Vehicle Routing Problem with Time Windows
Authors: 黃家耀
Wong Ka Io
國立交通大學運輸科技與管理學系(所)
Keywords: 等待策略;動態;即時需求;時窗限制下的車輛路線問題;Waiting Strategies;Dynamic;Real-time request;Vehicle Routing Problem withTimeWindows
Issue Date: 2008
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.
Gov't Doc #: NSC97-2221-E009-119
URI: http://hdl.handle.net/11536/101957
https://www.grb.gov.tw/search/planDetail?id=1690109&docId=291554
Appears in Collections:Research Plans


Files in This Item:

  1. 972221E009119.PDF

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.