Accueil
Affiche (PDF)
 
Participants
Programme
Inscription
Site
Hébergement
Liens
 
 
Éditions précédentes
2004
2003
2002


    

Séance TC10 - Tournées de véhicules V / Vehicle routing V

Jour mardi, le 10 mai 2005
Salle TAL Gestion globale d'actifs inc.
Président Karl F. Doerner

Présentations

15h30 The Probabilistic Traveling Salesman Problem with Deadlines
  Ann M. Campbell, University of Iowa, Management Sciences, Henry B. Tippie College of Business, Iowa City, IA, USA

Many delivery companies employ an a priori route which specifies an ordering of all possible customers that a driver may visit. Despite their common usage, the consideration of time constraints in a priori route construction is absent in the literature. We introduce the probabilistic traveling salesman problem with deadlines (PTSPD) and discuss the challenges of defining what it means to violate a deadline in a stochastic environment.


15h55 The Stochastic Dynamic Traveling Salesman Problem with Time Windows with Application to Just-In-Time Pickup/Delivery
  Tsung-Sheng Chang, National Dong Hwa University, Institute of Global Operations Strategy and Logistics Management, 1, Sec.2, Da-Hsueh Rd., Shou-Feng, Hualien, Taiwan, 974
Yat-Wah Wan, National Dong Hwa University, Institute of Global Operations Strategy and Logistics Management, 1, Sec.2, Da-Hsueh Rd., Shou-Feng, Hualien, Taiwan, 974

The Just-in-time (JIT) service capability has become a norm for freight carriers. In this paper, the JIT pickup/delivery problems are first formulated as stochastic dynamic traveling salesman problems with time windows (SDTSPTW). Efficient heuristics, as supported by numerical results, have been developed for these NP hard problems.


16h20 A Simulated Annealing Approach for Solving Vehicle Routing Problems with Time Windows
  Nilesh Laddhad, Concordia University, Mechanical and Industrial Engineering, 1455 de Maisonneuve W., Montreal, Quebec, Canada, H3G 1M8
Mingyuan Chen, Concordia University, Mechanical and Industrial Engineering, 1455 de Maisonneuve W., Montreal, Quebec, Canada, H3G 1M8

An integer programming model and a solution method based on simulated annealing (SA) are developed for solving a multi-vehicle vehicle routing problem with time windows. The method efficiently solved the problem for different data sets and the results were compared with optimal solutions for small size problems.


16h45 Stochastic Local Search Procedures for the ProbabilisticTwo-Day Vehicle Routing Problem
  Karl F. Doerner, University of Vienna, Production and Operations Management, Bruennerstrasse 72, A-1210 Vienna, Austria
Walter J. Gutjahr, University of Vienna, Statistics and Decision Support Systems, Vienna, Austria
Richard F. Hartl, University of Vienna, Production and Operations Management, Bruennerstrasse 72, A-1210 Vienna, Austria
Guglielmo Lulli, Università Milano, Informatica, Sistemistica e Comunicazione, Milano, Italy

This study is motivated by the study of a real-world application on blood delivery. The Austrian Red Cross (ARC), a non-profit organization, is in charge of delivering blood to hospitals on their request. To reduce their operating costs through higher flexibility, the ARC is interested in changing policy providing two different types of service: a urgent service which delivers the blood within one day and the other, regular service, within two days. Obviously the two services come at different prices. We formalize this problem as a stochastic problem, with the objective to minimize the average long-run delivery costs, knowing the probabilities governing the requests of service. To solve real instances of our problem in a reasonable time, we propose three heuristic procedures whose core routine is an Ant Colony Optimization algorithm, which differ from each other by the rule implemented to select the regular blood orders to serve immediately. We compare the three heuristics on both a set of real data and on set of randomly generated synthetic data. Computational results show the viability of our approach.