3 présentations

• 
  15h30 - 15h55

  Generalized Dial-A-Ride Problem on Road Networks with Time-dependent Travel Times

  • Bahman Bornay, prés., Polytechnique Montreal, CIRRELT, CTT
  • Michel Gendreau, Polytechnique Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT

  Classical pickup and delivery problem with time windows is usually formulated on a complete customer-based graph, wherein links between customer vertices represent the shortest paths between each pair of them, which might not capture the case we often face in real-life, where the speed on links changes over time affecting the travel times, thereby leading to multiple shortest paths within various intervals throughout a day. For any request, these problems also consider a single location for the pickup and a single location for the delivery. However, we argue that in a modern and increasingly competitive market, carrier companies might have to provide the clients with options to choose a few potential pickup and delivery locations among all others, each with its own time windows, based on their availability and constraints. In particular, in the case of a Dial-A-Ride problem (DARP), which generalizes the pickup and delivery problem with time windows, the latter service could be regarded as a requirement rather than a feature. The rich vehicle routing problem body of knowledge does not entail any article which explicitly investigate the combination of the aforementioned aspects. To fill this gap, we formally introduce a new class of DARP which assumes a set of potential pickup and delivery locations for each transit request, and call it a Generalized Dial-A-Ride problem (GDARP), which is studied on real road networks with time-dependent travel times. A MIP model is presented, and the scheduling problem for each vehicle is formulated as a dynamic programming (DP) problem, and is solved to optimality. We present an efficient DP-embedded hybrid metaheuristic which renders high-quality solutions.

• 
  15h55 - 16h20

  A capacitated multi-vehicle covering tour problem (m-CTP) with intermediate facilities for waste collection

  • Vera Fischer, prés., University of Fribourg
  • David Schindl, University of Fribourg
  • Antoine Legrain, Polytechnique Montréal
  • Meritxell Pacheco Paneque, University of Fribourg

  We consider a waste collection problem which consists in identifying locations of collection sites that cover all residential buildings (set cover) and creating collection routes with intermediate facilities for a vehicle at minimum total cost. We propose a mixed-integer linear programming (MILP) formulation that exploits the sparsity of the road network. To efficiently solve practical instances, we decompose the problem as follows: we solve a minimum clique covering problem on chordal graphs to identify the set covers and propose a column generation approach to build the routes for a given set cover.

• 
  16h20 - 16h45

  The design of territories and delivery schedules in attended home delivery

  • Jacques Renaud, prés., Université Laval, CIRRELT
  • Jean-François Côté, Université Laval
  • Joseph Robitaille, Université Laval

  The home delivery context brings several optimization challenges. When the presence of customers is required for the delivery to happen, the service provider and the customers must agree on a fixed delivery date and time. For the service provider, this leads to the problem of finding a schedule of economical time windows where the merchandise can be conveniently delivered. Typical approaches to find economical time windows work by using a set of predefined territories (e.g., zip codes) and finding the most cost-efficient time windows for those territories. Unfortunately, the zip codes, which are the most used, were not designed for the context of attended home delivery. This might lead to suboptimal solutions, hence, the expected travel distance might be higher. This work goes a step further by redesigning the territories to obtain more economical time windows for the service provider. Our approach works in two phases: in phase 1, we design territories in such way the amount of work in each territory is balanced and in phase 2, we try to find the lowest cost time windows for the given territories. Our computational results show the effectiveness of our approach.