Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching

Guertin, François; Potvin, Jean-Yves; Taillard, Éric
November 1999
Transportation Science;Nov99, Vol. 33 Issue 4, p381
Academic Journal
An abundant literature about vehicle routing and scheduling problems is available in the scientific community. However, a large fraction of this work deals with static problems where all data are known before the routes are constructed. Recent technological advances now create environments where decisions are taken quickly, using new or updated information about the current routing situation. This paper describes such a dynamic problem, motivated from courier service applications, where customer requests with soft time windows must be dispatched in real time to a fleet of vehicles in movement. A tabu search heuristic, initially designed for the static version of the problem, has been adapted to the dynamic case and implemented on a parallel platform to increase the computational effort. Numerical results are reported using different request arrival rates, and comparisons are established with other heuristic methods.


Related Articles

  • Diversion Issues in Real-Time Vehicle Dispatching. Ichoua, Soumia; Gendreau, Michel; Potvin, Jean-Yves // Transportation Science;Nov2000, Vol. 34 Issue 4, p426 

    Recent technological advances in communication systems now allow the exploitation of real-time information for dynamic vehicle routing and scheduling. It is possible, in particular, to consider diverting a vehicle away from its current destination in response to a new customer request. In this...

  • REAL-TIME PRODUCTION SCHEDULING OF AN AUTOMATED CARDLINE. Akella, R.; Choong, Y.; Gershwin, S. B. // Annals of Operations Research;1985, Vol. 3 Issue 1-4, p403 

    In this paper, we describe a flow model of an automated-printed circuit card assembly line at the International Business Machines Corporation (IBM) plant at Tucson, Arizona. We use a simulation based on this model as a test bed to discuss the performance of a hierarchical scheduling policy...

  • Scheduling Problem of Order Picking Operations Considering the Last Parcel Pickup Time. Shoya Yamada; Aya Ishigaki; Tetsuo Yamada; Taku Harada // Proceedings for the Northeast Region Decision Sciences Institute;2016, p1 

    Recently, a company that manages an EC site is considering a new service in order to get more customers. For example, those companies deal with online shop focus on the fastest shipping in order to attract customers. However, since many tasks are to be imposed upon delivery companies in order to...

  • Putting smaller repairs on the fast track. KEITH, BOB // Auto Body Repair Network;Dec2016, Vol. 35 Issue 12, p38 

    The article focuses on improving cycle time numbers in smaller jobs by providing express services in the automobile shops. It mentions three models used in express services including stand-alone facility which requires brick and mortar along with additional labours, dedicated internal fast lane...

  • An improved constraint satisfaction adaptive neural network for job-shop scheduling. Yang, Shengxiang; Wang, Dingwei; Chai, Tianyou; Kendall, Graham // Journal of Scheduling; 

    This paper presents an improved constraint satisfaction adaptive neural network for job-shop scheduling problems. The neural network is constructed based on the constraint conditions of a job-shop scheduling problem. Its structure and neuron connections can change adaptively according to the...

  • Specially structred flow shop scheduling with fuzzy processing time to minimimze the rental cost. Gupta, Deepak; Sharma, Sameer; Aggarwal, Shefali // Advances in Applied Science Research;Aug2012, Vol. 3 Issue 4, p1986 

    Scheduling is a enduring process where the existence of real time information frequently forces the review and modification of pre - established schedules. The real world is complex; complexity in the world generally arises from uncertainty. From this prospective, the concept of fuzzy...

  • Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. Chun-Lung Chen; Chuen-Lung Chen // International Journal of Advanced Manufacturing Technology;Oct2009, Vol. 43 Issue 1/2, p161 

    This paper proposes several hybrid metaheuristics for the unrelated parallel-machine scheduling problem with sequence-dependent setup times given the objective of minimizing the weighted number of tardy jobs. The metaheuristics begin with effective initial solution generators to generate initial...

  • An Optimization Approach to Solve a Multi-objective Unrelated Parallel Machine Scheduling Problem. Sadeghi, S.; Ariafar, Sh.; Ghanbari, M.; Ismail, N. // Applied Mechanics & Materials;2014, Issue 564, p585 

    In this study, a multi-objective optimization method for an unrelated parallel machine scheduling problem was addressed. The model, simultaneously takes into account the minimization of makespan and machine utilization cost. Then, because of the complexity of the problem, a heuristic algorithm...

  • ESTUDIO DE ALGORITMOS DINÁMICOS PARA EL PROBLEMA DE SECUENCIACIÓN DE TRABAJOS EN UNA MÁQUINA SIMPLE. Montoya Torres, Jairo Rafael; Rodríguez Verján, Gloria; Merchán Alba, Liliana // Ingeniería y Universidad;2006, Vol. 10 Issue 2, p1 

    classical scheduling theory has traditionally considered the study and evaluation of scheduling algorithms based on the hypothesis of perfect advanced knowledge of the information needed to make the sequencing decisions. These algorithms are called to be used in an off-line context. Recently, a...


Read the Article


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

Try another library?
Sign out of this library

Other Topics