TITLE

Hybrid Heuristics for the Vehicle Routing Problem with Time Windows

AUTHOR(S)
Russell, Robert A.
PUB. DATE
May 1995
SOURCE
Transportation Science;May95, Vol. 29 Issue 2, p156
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
This paper addresses the development of effective heuristics for solving the vehicle routing and scheduling problem with time window constraints. Both tour construction and local search tour improvement heuristics are developed. A major premise of the paper is that embedding global tour improvement procedures within the tour construction process can lead to improved solutions. Computational results are reported on test problems from the literature as well as real world applications. The hybrid construction / improvement heuristic is more effective in reducing vehicle fleet size requirements than previously reported heuristics.
ACCESSION #
4454114

 

Related Articles

  • Solving a general Routing and Scheduling Problem by Chain Decomposition and Tabu Search. Hooker, J. N.; Natraj, N. R. // Transportation Science;Feb95, Vol. 29 Issue 1, p30 

    We modify the classical chain decomposition model for vehicle routing in order to formulate a very general class of vehicle routing and scheduling problems with time windows, in which vehicles may pick up loads while on the way to deliver others. We use the model as a framework for a tabu search...

  • BATCHING AND SCHEDULING JOBS ON BATCH AND DISCRETE PROCESSORS. Ahmadi, Javad H.; Ahmadi, Reza H.; Dasu, Sriram; Tang, Christopher S. // Operations Research;Jul/Aug92, Vol. 40 Issue 4, p750 

    We consider a situation in which the manufacturing system is equipped with batch and discrete processors. Each batch processor can process a batch (limited number) of jobs simultaneously. Once the process begins, no job can be released from the batch processor until the entire batch is...

  • MINIMIZING CYCLE TIME IN A BLOCKING FLOWSHOP. Abadi, I. N. Kamal; Hall, Nicholas G.; Sriskandarajah, Chelliah // Operations Research;Jan/Feb2000, Vol. 48 Issue 1, p177 

    We consider a blocking (i.e., bufferless) flowshop that repetitively processes a minimal part set to minimize its cycle time, or equivalently to maximize its throughput rate. The best previous heuristic procedure solves instances with 9 machines and 25 jobs, with relative errors averaging about...

  • JACKSON'S RULE FOR SINGLE-MACHINE SCHEDULING: MAKING A GOOD HEURISTIC BETTER. Hall, Leslie A.; Shmoys, David B. // Mathematics of Operations Research;Feb92, Vol. 17 Issue 1, p22 

    We consider the scheduling problem in which jobs with release dates and delivery times are to be scheduled on one machine We present a &frac43;-approximation algorithm for the problem with precedence constraints among the jobs, and two polynomial approximation schemes for the problem without...

  • Two very large-scale neighborhoods for single machine scheduling. Brueggemann, Tobias; Hurink, Johann // OR Spectrum;Jul2007, Vol. 29 Issue 3, p513 

    In this paper, the problem of minimizing the total completion time on a single machine with the presence of release dates is studied. We introduce two different approaches leading to very large-scale neighborhoods in which the best improving neighbor can be determined in polynomial time....

  • HEURISTICS FOR SCHEDULING QUERY OPERATORS. Martincov√°, Penka // Proceedings of the International Conference on Systems for Autom;2005, p79 

    Scheduling problem is known to be NP-hard ant its optimal solution can be time consuming. The paper presents heuristic algorithm for SQL processing in distributed environment, which reduces execution time. In the paper we present results of experiments with various kind of query trees.

  • SIMULTANEOUS RESOURCE SCHEDULING TO MINIMIZE WEIGHTED FLOW TIMES. Dobson, Gregory; Karmarkar, Uday S. // Operations Research;Jul/Aug89, Vol. 37 Issue 4, p592 

    Many scheduling problems in manufacturing and service firms involve tasks that require more than one resource to be used simultaneously to execute the task. Two formulations of this scheduling problem are given. We develop a Lagrangian relaxation for the problem that has an intuitive...

  • A COMPARATIVE EVALUATION OF HEURISTIC LINE BALANCING TECHNIQUES. Talbot, F. Brian; Patterson, James H.; Gehrlein, William V. // Management Science;Apr1986, Vol. 32 Issue 4, p430 

    In this paper, we report on a computational experiment designed to assess the efficacy of 26 heuristic decision rules which group work tasks into work stations along an assembly line such that the number of work stations required is minimized. The heuristic decision rules investigated vary from...

  • ALGORITHMS FOR THE VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW CONSTRAINTS. Solomon, Marius M. // Operations Research;Mar/Apr87, Vol. 35 Issue 2, p254 

    This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety...

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