Waiting Strategies for Dynamic Vehicle Routing

Branke, J├╝rgen; Middendorf, Martin; Noeth, Guntram; Dessouky, Maged
August 2005
Transportation Science;Aug2005, Vol. 39 Issue 3, p298
Academic Journal
Many real-world vehicle routing problems are dynamic optimization problems, with customer requests arriving over time, requiring a repeated reoptimization. In this paper, we consider a dynamic vehicle routing problem where one additional customer arrives at a beforehand unknown location when the vehicles are already under way. Our objective is to maximize the probability that the additional customer can be integrated into one of the otherwise fixed tours without violating time constraints. This is achieved by letting the vehicles wait at suitable locations during their tours, thus influencing the position of the vehicles at the time when the new customer arrives. For the cases of one and two vehicles, we derive theoretical results about the best waiting strategies. The general problem is shown to be NP-complete. Several deterministic waiting strategies and an evolutionary algorithm to optimize the waiting strategy are proposed and compared empirically. I is demonstrated that a proper waiting strategy can significantly increase the probability of being able to service the additional customer, at the same time reducing the average detour to serve that customer.


Related Articles

  • Ant Colony Optimization for Capacitated Vehicle Routing Problem. Tan, W. F.; Lee, L. S.; Majid, Z. A.; Seow, H. V. // Journal of Computer Science;2012, Vol. 8 Issue 6, p846 

    Problem statement: The Capacitated Vehicle Routing Problem (CVRP) is a well-known combinatorial optimization problem which is concerned with the distribution of goods between the depot and customers. It is of economic importance to businesses as approximately 10-20% of the final cost of the...

  • Solution and Level Identification of Sudoku Using Harmony Search. Nath Mandal, Satyendra; Sadhu, Saumi // International Journal of Modern Education & Computer Science;Apr2013, Vol. 5 Issue 3, p49 

    Different optimization techniques have been used to solve Sudoku. Zong Woo Geem have applied harmony search in Sudoku to get better result. He has taken a Sudoku and time complexity has been optimized by different values of parameters. But, he has not given way of solution in details. He has...

  • Gravitation field algorithm and its application in gene cluster. Ming Zheng; Gui-xia Liu; Chun-guang Zhou; Yan-chun Liang; Yan Wang // Algorithms for Molecular Biology;2010, Vol. 5, p32 

    Background: Searching optima is one of the most challenging tasks in clustering genes from available experimental data or given functions. SA, GA, PSO and other similar efficient global optimization methods are used by biotechnologists. All these algorithms are based on the imitation of natural...

  • Modified Harmony Search Algorithm for the Capacitated Vehicle Routing Problem. Pichpibul, Tantikorn; Kawtummachai, Ruengsak // International MultiConference of Engineers & Computer Scientists;2013, Vol. 2, p1 

    This paper presents the modification of a harmony search algorithm (HS) for the capacitated vehicle routing problem (CVRP). The objective is to find a feasible set of vehicle routes that minimizes the total traveling distance and the number of vehicles used. The modified HS has two stages....

  • Application of Dijkstra Algorithm in Logistics Distribution Lines. Liu Xiao-Yan; Chen Yan-Li // Proceedings of the International Symposium on Computer Science &;Aug2010, Vol. 2 Issue 1, p48 

    Use heap sort to sort unlabeled nodes in geography network to improve the efficiency of Dijkstra algorithm. Provide separate solutions of path optimization based on Dijkstra algorithm in logistics distribution lines with barriers and no barriers. Propose modified Dijkstra algorithm given...

  • A Hybrid Heuristic Approach to Solve the Capacitated Vehicle Routing Problem. Bouhafs, Lyamine; Hajjam, Amir; Koukam, Abder // Journal of Artificial Intelligence: Theory & Application;Feb2010, Vol. 1 Issue 1, p31 

    In this paper, we propose a hybrid approach for solving the capacitated vehicle routing problem. We combine an Ant Colony System (ACS) algorithm with a Savings algorithm and, then, we improve solutions by a local search heuristic. The Ant Colony System is a distributed system that combines an...

  • Dual methods for probabilistic optimization problems*. Dentcheva, Darinka; Lai, Bogumila; Ruszczynski, Andrzej // Mathematical Methods of Operations Research;2004, Vol. 60 Issue 2, p331 

    We consider nonlinear stochastic optimization problems with probabilistic constraints. The concept of ap-efficient point of a probability distribution is used to derive equivalent problem formulations, and necessary and sufficient optimality conditions. We analyze the dual functional and its...

  • Suboptimal control of logical-dynamic systems under parametric uncertainty conditions. Bortakovskii, A. // Automation & Remote Control;Nov2007, Vol. 68 Issue 11, p1986 

    Sufficient optimality conditions of logical-dynamic systems are obtained, the logical portion of which models the operation of a memory-equipped automaton. Equations are derived for the definition of the optimal programmed control and full feedback control. Optimal processes with multiple...

  • Bidding-based multi-agent system for integrated process planning and scheduling: a data-mining and hybrid tabu-SA algorithm-oriented approach. Shukla, Sanjay; Tiwari, M.; Son, Young // International Journal of Advanced Manufacturing Technology;Aug2008, Vol. 38 Issue 1/2, p163 

    This paper conceptualizes a bidding-based multi-agent system for solving integrated process-planning and scheduling problem. The proposed architecture consists of various autonomous agents capable of communicating (bidding) with each other and making decisions based on their knowledge. Moreover,...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics