The problem of the on-line version of the vehicle routing problem with time windows (VRPTW) differs from the traditional off-line problem in the dynamical arrival of requests and the execution of the partial tour during the run time. The study develops an on-line optimization-based heuristic that combined the concepts of the “on-line algorithm,” “anytime algorithm,” and local search heuristics to solve the on-line version of VRPTW. The solution heuristic is evaluated with modified Solomon’s problems. By comparing with these benchmark problems, the different results between on-line and off-line algorithms are indicated.
Get full access to this article
View all access options for this article.
References
1.
PsaraftisH. N.Dynamic Vehicle-Routing—Status and Prospects. Annals of Operations Research, Vol. 61, 1995, pp. 143–164.
2.
SolomonM. M.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, Vol. 35, No. 2, 1987, pp. 254–265.
3.
ReganA. C., MahmassaniH. S., and JailletP.. Improving Efficiency of Commercial Vehicle Operations Using Real-Time Information: Potential Uses and Assignment Strategies. In Transportation Research Record 1493, TRB, National Research Council, Washington, D.C., 1995, pp. 188–198.
4.
ReganA. C., MahmassaniH. S., and JailletP.. Dynamic Decision Making for Commercial Fleet Operations Using Real-Time Information. In Transportation Research Record 1537, TRB, National Research Council, Washington, D.C., 1996, pp. 91–97.
5.
PsaraftisH. N.Dynamic Vehicle Routing Problems. In Vehicle Routing: Methods and Studies (GoldenB. L. and AssadA. A., eds.), North Holland, Amsterdam, 1988, pp. 223–248.
6.
BertsimasD. J., and van RyzinG.. A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane. Operations Research, Vol. 39, No. 4, 1991, pp. 601–615.
7.
HallR. W.Pickup and Delivery Systems for Overnight Carriers. Transportation Research, Vol. 30A, No. 3, 1996, pp. 173–187.
8.
SgallJ.Randomized On-Line Scheduling of Parallel Jobs. Journal of Algorithms, Vol. 21, No. 1, 1996, pp. 149–175.
9.
DeanT. L., and BoddyM.. An Analysis of Time-Dependent Planning. Proc., 7th National Conference on Artificial Intelligence, Minneapolis, Minn., 1988, pp. 49–54.
10.
ZilbersteinS., and RussellS.. Optimal Composition of Real-Time Systems. Artificial Intelligence, Vol. 82, No. 1, 1996, pp. 181–213.
11.
OrI.Traveling Salesman—Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking. Ph.D. dissertation.Department of Industrial Engineering and Management Science, Northwestern University, Evanston, Ill., 1976.
12.
RochatY., and TaillardE.. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, Vol. 1, No. 1, 1995, pp. 147–167.
