4 présentations

• 
  15h30 - 15h55

  Crowdkeeping in Last-mile Delivery

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

  In order to improve the efficiency of the last-mile delivery system when customers are possibly absent for deliveries, we propose the idea of employing the crowd to work as keepers and to provide storage services for their neighbors. Crowd keepers have extra flexibility, more availability, and lower costs than fixed storage such as automated lockers, and this leads to a more efficient and a more profitable system for last-mile deliveries. We present a bilevel program that jointly determines the assignment, routing, and pricing decisions while considering customer preferences, keeper behaviors, and platform operations. We develop an equivalent single-level program, a mixed-integer linear program with subtour elimination constraints, that can be solved to optimality using a row generation algorithm. To improve the efficiency of the solution procedure, we further derive exact best response sets for both customers and keepers, and approximate optimal travel times using linear regression. We present a numerical study using a real-world dataset from Amazon. The fixed-storage and the no-storage systems are used as benchmarks to assess the performance of the crowdkeeping system. The results show that the crowdkeeping delivery system has the potential to generate higher profits due to its ability to consolidate deliveries and to eliminate failed deliveries.

• 
  15h55 - 16h20

  Dynamic Single Facility Location under Cumulative Customer Demand

  • Warley Almeida Silva, prés., Université de Montréal
  • Margarida Carvalho, Université de Montréal
  • Sanjay Dominik Jena, Université du Québec à Montréal

  Dynamic facility location problems aim to place valuable resources over time, while optimizing some performance measure based on customer demand. Most works ignore the effects of unmet demand at some time period on location decisions of subsequent time periods, either by requiring customer demand to be served or by assuming that it vanishes when not served. However, there are many real-world applications where unmet demand carries over to future time periods. In this sense, this work studies a novel location problem, where the decision maker moves a single facility over time to capture cumulative customer demand. We propose two formulations for this problem, and show that one has a continuous relaxation strictly tighter than the other. We characterize the computational complexity, and develop a branch-and-Benders-cut algorithm based on the tightest formulation, where optimality cuts are computed through an analytical procedure. Computational experiments show that our method is approximately 20 times faster than solving the tighter formulation directly, besides proving smaller optimality gaps within the same time limit. Our results also highlight the benefit of accounting for cumulative customer demand within formulations, since our policies perform much better than those obtained by ignoring cumulative customer demand or employing intuitive heuristics.

• 
  16h20 - 16h45

  Neural Network Estimators for Optimal Tour Lengths of Traveling Salesperson Problem Instances with Arbitrary Node Distributions

  • Taha Varol, prés., HEC Montreal
  • Okan Örsan Özener, Özyeğin University
  • Erinç Albey, Özyeğin University

  To enhance operational efficiency in logistics, solving complex routing problems is crucial. However, conventional two-phase frameworks, which cluster locations first and then determine routes, can be highly suboptimal due to the initial clustering phase. To address this, we propose a less myopic approach by leveraging information on optimal tour lengths of potential clusters. Our method employs accurate Traveling Salesperson Problem (TSP) tour length estimators based on neural networks (NNs), combining NNs with domain knowledge in routing. By incorporating node-level, instance-level, and solution-level features, we achieve predictions deviating by less than 0.7% from optimality on average. Unlike prior studies, we design new instances replicating real logistics networks, posing significant computational challenges. To tackle this, we develop an efficient method for obtaining lower bounds and partial TSP solutions, which are used as solution-level predictors. Computational tests show our method outperforms existing ML approaches by up to six times on training instances and up to 100 times on out-of-distribution test instances. Integrating our ML models with metaheuristics yields an enumeration-like solution framework, significantly improving solution quality and time efficiency compared to state-of-the-art solvers. Our study highlights the potential of proposed features, estimation models, and methodology in addressing the challenges of massive-scale route planning problems.

• 
  16h45 - 17h10

  A contextual framework for learning routing experiences in last-mile delivery

  • Huai Sun, Student
  • Okan Arslan, prés., GERAD, HEC Montréal

  We present a contextual framework for solving the data-driven traveling salesman problem in last-mile delivery. The objective of the framework is to generate routes similar to historical high-quality ones, as classified by operational experts, by considering the unstructured and complex features of last-mile delivery operations. The framework involves learning a transition likelihood matrix between customer stops and using a classical TSP solver to generate routes similar to those high-quality routes in a given dataset. We employ feature-based factorization of the transition likelihood matrix, which reduces the dimensions of the information to be learned. We develop a derivative-free algorithm by extending the coordinate search method and a complementary method for learning the transitions directly from the data. We test the efficiency of the methods using a case study based on the Amazon Last-Mile Routing Challenge and show that our methods are effective, interpretable, and flexible. A preliminary version of our methods achieved third place in the aforementioned challenge. We improve on this result by 33% in an out-of-sample dataset. Furthermore, our best-performing method improves the best score in the literature achieved on the available training dataset by 42%.