4 Presentations

• 
  10:30 AM - 10:55 AM

  Robust Probabilistic Envelope Constrained Programming for Ultra-fast Delivery

  • Xin Wang, presenter,
  • Erick Delage, GERAD, HEC Montréal
  • Okan Arslan, GERAD, HEC Montréal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

  Abstract:
  Ultra-fast delivery is a novel idea for food and grocery delivery service within a matter of minutes. We investigate the arising delivery problem with different service level guarantees, and develop a probabilistic envelope constrained (PEC) programming model in which the demand depends on the uncertain delivery time and on the allocation decisions. We also develop robust PEC programming models in which both the distribution of the driving speed and the probability of customer placing order in different time periods are not explicitly known. We then derive equivalent and tractable linear programming models and solve the ultra-fast delivery problem for different service levels. We compare the performances of these service levels under different protections, and find the profitable ones that yield a fast delivery, a high demand coverage, and low level of violations. We carry out extensive experiments on a real-world dataset provided by Amazon and Google API, and obtain the managerial insights.

  Keywords:
  ultra-fast delivery, service level, probabilistic envelope constraint, robust optimization
• 
  10:55 AM - 11:20 AM

  Solving the Park-and-loop Routing Problem by Branch-price-and-cut

  • Nicolas Cabrera, presenter, HEC Montréal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
  • Jorge Mendoza, HEC Montréal

  The park-and-loop routing problem is a variation of the vehicle routing problem in which routes include a main tour that is completed using a vehicle and subtours that are carried out on foot after parking the vehicle. Additionally, the route duration and total walking distance are bounded. To solve the problem, we propose an exact solution method based on the branch-price-and-cut framework. Our method uses problem-specific components to solve the pricing problem. We report on computational experiments carried out on a standard set of 40 instances with up to 50 customers. The results show that our method delivers solutions that compare favorably to existing metaheuristic algorithms, matching all previously best-known solutions and improving 11 of them in reasonable computational times. Moreover, our method provides optimality certificates for 39 out of the 40 instances.
• 
  11:20 AM - 11:45 AM

  Parameter Optimization in Data-driven Vehicle Routing in Last Mile Delivery

  • Huai Sun, presenter, Student
  • Okan Arslan, GERAD, HEC Montréal

  This talk is about a methodological approach developed for the Amazon Last Mile Routing Research Challenge in 2021. The primary goal of this challenge was to develop innovative approaches to produce solutions to the route sequencing problem. To this end, we originally developed a prescriptive method based on rules that are extracted through descriptive analysis of the data. The key rule was to discourage the zone transitions on the generated routes by multiplying the distances by some penalty terms. Selecting custom values for these penalties resulted in a third place in the competition. In this follow up study, we have extended our research to calculate specific zone transition multipliers, unique to individual stations. While this method requires searching a large solution space for each unique station, we show that it is possible to improve the results compared to the naïve version.
• 
  11:45 AM - 12:10 PM

  Opportunity Sales in Attended Home Delivery

  • Celen Naz Otken, Koc University
  • Baris Yildiz, Koc University
  • Okan Arslan, presenter, GERAD, HEC Montréal
  • Gilbert Laporte, HEC Montréal

  We present a new business model for e-groceries, which exploits idle times and underutilized vehicle capacities to generate extra profits through opportunity sales. We consider nudging potential target customers (residing in locations that are "easy" to insert into the delivery tours) with push notifications to generate new sales. These customers are incentivized for purchases by dropping the terms imposed on standard e-grocery sales such as service fees or minimum purchase quantities. Managing the delivery operations for this innovative business model requires concurrently choosing the target customers and planning the vehicle routes under the offer acceptance and response time uncertainties. We decompose the problem into a routing problem and several customer selection problems. For the solution to the customer selection problems, we propose mathematical models with varying risk-taking levels. We also investigate the benefits of dynamic policies to take advantage of the information revealed during the delivery operations in order to adjust customer selection and vehicle routing decisions. Our extensive numerical experiments show that these models, equipped with dynamic decision making, can compete with the risk-ignorant models for the total profit while generating more sales per offer, as well as ensuring timely execution of the delivery operations.