4 Presentations

• 
  10:30 AM - 10:55 AM

  Increasing schedule reliability in the multi-depot vehicle scheduling problem with stochastic travel time

  • Léa Ricard, presenter, Université de Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Andrea Lodi, University of Bologna
  • Louis-Martin Rousseau, Polytechnique Montréal

  One of the attributes of public transport service that is most important to riders is the variability of travel times. Thus, many bus operators are trying to increase the regularity of their service, also referred to as reliability. Our work explores methods to potentially improve service reliability in the operational planning stage using a data-driven approach. First, travel time distributions are predicted using historical Automatic Vehicle Location (AVL) data. These predictions are then integrated in the reliable multi-depot vehicle scheduling problem with stochastic travel time (R-MDVSP-STT) which aims to build vehicle schedules that are both cost- and delay-efficient. Experimental results with real data collected by buses running in Montréal (Canada) indicate that the R-MDVSP-STT provides more reliable vehicle schedules for a negligible increase in operational costs compared to the multi-depot vehicle scheduling problem.

• 
  10:55 AM - 11:20 AM

  Crowd-shipping: An Open VRP Variant with Stochastic Destinations

  • Michel Gendreau, presenter, Polytechnique Montréal
  • Fabian Torres, Polytechnique Montreal
  • Walter Rei, Université du Québec à Montréal

  We consider a problem setting in which a Crowd-Shipping Platform(CSP) must deliver heterogeneous packages to customers from a central depot over a wide geographic area using a fleet of professional vehicles (PV) and a pool of Occasional Drivers (OD). Delivery requests are characterized by their volume, a time window, and the sector of the city of the delivery point. The minimum capacity of all OD vehicles is known. The supply of ODs on a given day is unknown at the planning stage, but probabilistic information is available.
  We consider a two-stage stochastic model with recourse: in the first stage, routes are created at for both ODs and PVs, without knowledge of the supply of ODs or their destinations. In the second stage, routes are assigned to ODs as they arrive. ODs' routes that are not fulfilled, due to the lack of supply of ODs, must be assigned to PVs with a penalty α, as a recourse action.
  We rely on a set partitioning formulation, which is solved exactly through a column generation procedure imbedded in a Branch-and-Price framework. We have also implemented heuristics. Detailed results of computational experiments performed on instances having between 25 and 100 customers will be presented.

• 
  11:20 AM - 11:45 AM

  A Hub Location Routing Problem in the New Carrier Economy

  • Ivan Contreras, Concordia University
  • Ana María Anaya Arenas, ESG - UQAM
  • Sara Ahmed, presenter, Concordia University

  In the e-commerce and parcel delivery industries, customers are demanding greater flexibility and lower delivery time. The challenging distribution requirements forces companies to rethink their distribution network to face the new challenges in a cost efficient way. The current practices, including optimizing the design of the distribution network and the routing of the vehicle fleets are essential, but not sufficient on their own. Examples like Amazon and Flip-Kart show that adopting outsourcing strategies can play a key role for business's competitive survival, in today's volatile delivery environment. We hence propose a new multi-commodity model that considers simultaneously the hub location and routing decisions for a distribution network, while optimizing the option of using a common carrier for some of the commodities. Furthermore, if a parcel is delivered through a carrier, we model the selection and routing to the carrier collection point. We propose two matheuristic algorithms to solve the model. The first is a slope scaling matheuristic iteratively solving minimum cost flow and a multi-commodity arc location routing sub-problems. Secondly, we solve an integer programming scheme where smaller instances of the original problem are solved sequentially with a fix-and-optimize technique.

• 
  11:45 AM - 12:10 PM

  Branch-and-Cut-and-Price for the Electric Vehicle Routing Problem with Time Windows, Piecewise-Linear Recharging and Capacitated Recharging Stations

  • Guy Desaulniers, presenter, GERAD - Polytechnique Montréal
  • Edward Lam, Monash University
  • Peter J. Stuckey, Monash University

  The Electric Vehicle Routing Problem with Time Windows, Piecewise-Linear Recharging and Capacitated Recharging Stations aims to design minimum-cost routes for a fleet of electric vehicles subject to intra-route and inter-route constraints. Every vehicle is equipped with a rechargeable battery that depletes while it travels along its route. A vehicle must detour to a recharging station to recharge before draining its battery. To approximate a real recharging process, the amount of energy restored is modeled as a piecewise-linear function of the time spent recharging. In addition, each station is limited to a small number of chargers, and hence, when and where a vehicle can recharge must be scheduled around the availability of a charger. This talk proposes a branch-and-cut-and-price algorithm that designates the routing parts to integer programming using Dantzig-Wolfe decomposition and the scheduling parts to constraint programming using logic-based Benders decomposition. Experimental results indicate that this hybrid method can solve instances with up to 100 customers.