4 présentations

• 
  10h30 - 10h55

  Fairness Over Time Allocation in Traveling Salesman Problem

  • Guanyi Wang, prés., Polytechnique Montréal
  • Sriram Sankaranarayanan, IIM Ahmedabad
  • Andrea Lodi, Polytechnique Montreal

  This paper studies a variant of the traveling salesman problem (TSP) -- Fairness Over Time Allocation Traveling Salesman Problem (FOTA-TSP). Unlike TSP, whose target is to minimize the total cost of one TSP tour, FOTA-TSP is a multiple decision-making problem in which decisions (feasible TSP tours) are made/computed repeatedly in a given time period to minimize the total/average unfairness for reasonable metrics of unfairness. We propose a framework formulated via a mixed integer programming for the FOTA-TSP. We show that: for any constant $\epsilon > 0$, one can establish a sequence of feasible TSP solutions which ensures an $\epsilon$-additive-approximation error on the total/average unfairness for FOTA-TSP within $O(1/\epsilon)$ periods. We apply this framework to some typical TSP applications and provide a computationally efficient heuristic method to solve the above applications. Numerical results are reported to demonstrate the efficiency of the proposed method compared with naive approaches.

• 
  10h55 - 11h20

  An approach to learn drivers' implicit knowledge in the Traveling Salesman Problem with Time Windows

  • Jorge Mortes Alcaraz, prés., IMT Atlantique

  For some problems, we generally know the structure of the problem (i.e., the objective function to optimize and the constraints to respect), but we may be missing some contextual elements (e.g., some parameters of the model) since they may be too difficult or impossible to collect. Furthermore, users of the optimization system generally have tacit knowledge due to their experience. They are, thus, generally able to adapt the proposed solution in accordance with this tacit knowledge. They may, however, do this in a sub-optimal way.
  In terms of the Traveling Salesman Problem with Time Windows (TSP-TW), this implicit knowledge can be measured in how different are the routes that companies propose to drivers and the routes that these drivers do. We implement two Reinforcement Learning techniques that will learn from driver’s routes and will incorporate this tacit knowledge into a TSP-TW model. With the combination of Machine Learning and Operation Research techniques, we will be able to offer a procedure that adapts over time to the driver’s knowledge while minimizing route duration. To illustrate how the algorithms can learn over time, we will show a results comparison with some baseline benchmarks over instances with up to 100 customers.

• 
  11h20 - 11h45

  Crowdkeeping in Last-mile Delivery

  • Xin Wang, prés.,
  • Okan Arslan, GERAD, HEC Montréal
  • Erick Delage, GERAD, HEC Montréal

  To improve the efficiency of last-mile deliveries when customers are possibly absent from their homes, we propose the idea of employing the crowd to work as keepers and provide storage service. Crowd keepers have much flexibility, high mobility, large availability, and potentially lead to lower costs. We develop a bi-level model by considering customer preferences, keeper behaviors, platform operations, and the participants' coordination by jointly determining the location, assignment, routing, and pricing decisions. To get a tractable formulation, KKT conditions can be applied to derive an equivalent single-level model when the customer model and the keeper model are integral. This reformulated single-level model is a quadratic mixed-integer program with sub-tour elimination constraints and can be solved to optimality using a row generation algorithm. To improve the efficiency of the solution procedure even more but not to sacrifice the accuracy too much, an approximation model is developed for the bi-level model by estimating the travel time with a continuous approximation and by deriving the best responses of customers and keepers. We implement computational studies on a dataset provided by Amazon and find out the conditions where the crowd-keeper system performs better than the fixed-storage system and the no-storage system.

• 
  11h45 - 12h10

  Data-driven vehicle routing in last mile delivery

  • Okan Arslan, prés., GERAD, HEC Montréal
  • Rasit Abay, UNSW Canberra

  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 develop a prescriptive method based on rules that are extracted through descriptive analysis of the data. The method involves solving the traveling salesman problem on a transformed graph. The method is effective in generating high-quality solutions. This method received the third place in the routing challenge.