Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints

Ibaraki, T.; Imahori, S.; Kubo, M.; Masuda, T.; Uno, T.; Yagiura, M.
May 2005
Transportation Science;May2005, Vol. 39 Issue 2, p206
Academic Journal
We propose local search algorithms for the vehicle routing problem with soft time-window constraints. The time-window constraint for each customer is treated as a penalty function, which is very general in the sense that it can be nonconvex and discontinuous as long as it is piecewise linear. In our algorithm, we use local search to assign customers to vehicles and to find orders of customers for vehicles to visit. Our algorithm employs an advanced neighborhood, called the cyclic-exchange neighborhood,in addition to standard neighborhoods for the vehicle routing problem. After fixing the order of customers for a vehicle to visit, we must determine the optimal start times of processing at customers so that the total penalty is minimized. We show that this problem can be efficiently solved by using dynamic programming, which is then incorporated in our algorithm. We report computational results for various benchmark instances of the vehicle routing problem. The generality of time-window constraints allows us to handle a wide variety of scheduling problems. As an example, we mention in this paper an application to a production scheduling problem with inventory cost, and report computational results for real-world instances.


Related Articles

  • Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles. Zeng, Chengkuan; Tang, Jiafu; Yan, Chongjun // Journal of Intelligent Manufacturing;Oct2015, Vol. 26 Issue 5, p845 

    This paper addresses part scheduling problems (CPS problems) in the context of the need for exceptional parts to visit machines among cells and to be transferred via an automated guided vehicle (AGV) in order to minimize the process make-span. A nonlinear mathematical programming model is...

  • Energy-aware disk scheduling for soft real-time I/O requests. Youjip Won; Jongmin Kim; Wonmin Jung // Multimedia Systems;Feb2008, Vol. 13 Issue 5/6, p409 

    Abstract  In this work, we develop energy-aware disk scheduling algorithm for soft real-time I/O. Energy consumption is one of the major factors which bar the adoption of hard disk in mobile environment. Heat dissipation of large scale storage system also calls for an...

  • Single-machine scheduling to minimize maximum tardiness with minimum number of tardy jobs. Gupta, J. N. D.; Hariri, A. M. A.; Potts, C. N. // Annals of Operations Research;1999, Vol. 92 Issue 1-4, p107 

    This paper develops a branch and bound algorithm for solving the single-machine scheduling problem with the objective of minimizing the maximum tardiness of any job, subject to the constraint that the total number of tardy jobs is minimum. The algorithm uses a new lower bounding scheme, which is...

  • A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem. Hadjar, Ahmed; Marcotte, Odile; Soumis, François // Operations Research;Jan/Feb2006, Vol. 54 Issue 1, p130 

    We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, variable fixing, and cutting planes. We show that the solutions of the linear relaxation of the MDVSP contain many "odd cycles." We derive a...

  • FIXED JOB SCHEDULING WITH TWO TYPES OF PROCESSORS. Dondet, V. R.; Emmons, Hamilton // Operations Research;Jan/Feb92 Supplement 1, Vol. 40 Issue 1, p76 

    We consider a scheduling problem that involves two types of processors, but three types of jobs. Each job has a fixed start time and a fixed completion time, and falls into one of three types. Jobs of type 1 can be done only by type-1 processors, type-2 jobs only by type-2 processors, and type-0...

  • A NEW ALGORITHM FOR THE QUASI-ASSIGNMENT PROBLEM. Tiantai Song; Li Zhou // Annals of Operations Research;1990, Vol. 24 Issue 1-4, p205 

    The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasi-assignment problem. The algorithm is a...

  • ON THE EXACT UPPER BOUND FOR THE MULTIFIT PROCESSOR SCHEDULING ALGORITHM. Minyi Yue // Annals of Operations Research;1990, Vol. 24 Issue 1-4, p233 

    We consider the well-known problem of scheduling n independent tasks nonpreemptively on m identical processors with the aim of minimizing the makespan. Coffman, Garey and Johnson [1] described an algorithm, MULTIFTT, based on techniques from bin-packing, with better worst performance than the...

  • Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem. Mokotoff, E.; Jimeno, J. L. // Annals of Operations Research;Nov2002, Vol. 117 Issue 1-4, p133 

    The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration....

  • Container loading and unloading scheduling for a Mobile Harbor system: a global and local search method. Shin, Kyuhyeon; Lee, Taesik // Flexible Services & Manufacturing Journal;Dec2013, Vol. 25 Issue 4, p557 

    Mobile Harbor (MH) is a type of mobile floating port system with an on-board crane for off-shore container handling capability. Due to its unique operational features, it creates a new type of operational scheduling problem. Container loading and unloading sequence schedule for the MH on-board...


Read the Article


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

Try another library?
Sign out of this library

Other Topics