TITLE

A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows

AUTHOR(S)
Bent, Russell; Van Hentenryck, Pascal
PUB. DATE
November 2004
SOURCE
Transportation Science;Nov2004, Vol. 38 Issue 4, p515
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
The vehicle routing problem with time windows is a hard combinatorial optimization problem that has received considerable attention in the last decades. This paper proposes a two-stage hybrid algorithm for this transportation problem. The algorithm first minimizes the number of vehicles, using simulated annealing. It then minimizes travel cost by using a large neighborhood search that may relocate a large number of customers. Experimental results demonstrate the effectiveness of the algorithm, which has improved 10 (17%) of the 56 best published solutions to the Solomon benchmarks, while matching or improving the best solutions in 46 problems (82%). More important perhaps,the algorithm is shown to be very robust. With a fixed configuration of its parameters, it returns either the best published solutions (or improvements thereof) or solutions very close in quality on all Solomon benchmarks. Very preliminary results on the extended Solomon benchmarks are also given.
ACCESSION #
15253570

 

Related Articles

  • SOLVING A NEW PRIORITY M/M/C QUEUE MODEL FOR A MULTIMODE HUB COVERING LOCATION PROBLEM BY MULTI-OBJECTIVE PARALLEL SIMULATED ANNEALING. SEDEHZADEH, Samaneh; TAVAKKOLI-MOGHADDAM, Reza; MOHAMMADI, Mehrdad; JOLAI, Fariborz // Economic Computation & Economic Cybernetics Studies & Research;2014, Vol. 48 Issue 4, p288 

    In this paper, a new priority M/M/c queuing hub covering problem is presented, in which products with high priority are selected for service ahead of those with low priority. In addition, a mixed-integer nonlinear mathematical programming model is presented to find a good solution of the given...

  • Editorial. Williams, D. // Transactions of the Institute of Measurement & Control;2000, Vol. 22 Issue 2, p123 

    Editorial. Comments on the superior performance of genetic algorithms over the traditional search methods. Utilization of candidate solutions; Effectivity of schedule optimization system for manufacturing; Use of genetic algorithms and simulated annealing to schedule the maintenance of power...

  • A new multiobjective simulated annealing algorithm. Ozan Tekinalp // Journal of Global Optimization;Sep2007, Vol. 39 Issue 1, p49 

    Abstract  A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function...

  • PedMine--a simulated annealing algorithm to identify maximally unrelated individuals in population isolates. Julie A. Douglas; Conner I. Sandefur // Bioinformatics;Apr2008, Vol. 24 Issue 8, p1106 

    Summary: In family-based genetic studies, it is often useful to identify a subset of unrelated individuals. When such studies are conducted in population isolates, however, most if not all individuals are often detectably related to each other. To identify a set of maximally unrelated (or...

  • Study on Optimization of Railway Passenger Train Sets Assignment. Changfeng Zhu; Deyuan Liu; Linna Cheng; Haijun Li // Information Technology Journal;2013, Vol. 12 Issue 6, p1251 

    The passenger train sets is the carrier of railway passenger transport production and reasonable use of the passenger train sets is one of the key goals of railway transportation plan. In order to improve the operation efficiency of passenger train sets, optimization model of railway passenger...

  • Optimization on Placing-in and Taking-out Operation for Railway Special Line Based on Improved Simulated Annealing Algorithm. Deyuan Liu; Changfeng Zhu; Linna Cheng; Haijun Li // Information Technology Journal;2013, Vol. 12 Issue 6, p1257 

    Placing-in and taking-out operation of railway special line is one of the key links and also is a complicated system engineering that is influenced by multitudinous factors. The intrinsic mechanism of placing-in and taking-out operation for railway radial special line was analyzed according to...

  • Minimal cost linkages in graphs. Harrison, S. A.; Rayward-Smith, V. J. // Annals of Operations Research;1999, Vol. 86 Issue 1-4, p295 

    In this paper, we consider the problem of finding minimal cost linkages in graphs. We discuss how this problem arises in practice and, in particular, its relevance to the military. Given a graph G with an associated cost function and a multiset of vertex pairs, we address the problem of finding...

  • Bi-objective bimodal urban road network design using hybrid metaheuristics. Miandoabchi, Elnaz; Farahani, Reza; Szeto, W. // Central European Journal of Operations Research;Dec2012, Vol. 20 Issue 4, p583 

    In this paper a bimodal discrete urban road network design problem with bus and car modes is investigated. The problem consists of decision making for lane addition to the existing streets, new street constructions, converting some two-way streets to one-way streets, lane allocation for two-way...

  • An Efficient Solution Method for 0-1 Random Fuzzy Programming Problems Considering the Relaxation Problems. Hasuike, T.; Ishii, H.; Katagiri, H. // Open Operational Research Journal;2008, Vol. 2, p38 

    This paper considers a general 0-1 random fuzzy programming problem including some previous 0-1 stochastic and fuzzy programming problems. The proposal problem is not a well-defined problem due to including random fuzzy variables. Therefore, by introducing chance constraint and fuzzy goal for...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

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

Try another library?
Sign out of this library

Other Topics