Inverse Optimization for Routing Problems

• URL: http://arxiv.org/abs/2307.07357v3
• Date: Tue, 18 Jun 2024 19:18:16 GMT
• Title: Inverse Optimization for Routing Problems
• Authors: Pedro Zattoni Scroccaro, Piet van Beek, Peyman Mohajerin Esfahani, Bilge Atasoy,
• Abstract summary: We propose a method for learning decision-makers' behavior in routing problems using Inverse Optimization (IO) Our examples and results showcase the flexibility and real-world potential of the proposed IO methodology to learn from decision-makers' decisions in routing problems.
• Score: 3.282021317933024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a method for learning decision-makers' behavior in routing problems using Inverse Optimization (IO). The IO framework falls into the supervised learning category and builds on the premise that the target behavior is an optimizer of an unknown cost function. This cost function is to be learned through historical data, and in the context of routing problems, can be interpreted as the routing preferences of the decision-makers. In this view, the main contributions of this study are to propose an IO methodology with a hypothesis function, loss function, and stochastic first-order algorithm tailored to routing problems. We further test our IO approach in the Amazon Last Mile Routing Research Challenge, where the goal is to learn models that replicate the routing preferences of human drivers, using thousands of real-world routing examples. Our final IO-learned routing model achieves a score that ranks 2nd compared with the 48 models that qualified for the final round of the challenge. Our examples and results showcase the flexibility and real-world potential of the proposed IO methodology to learn from decision-makers' decisions in routing problems.

Related papers

• Making Large Language Models Better Planners with Reasoning-Decision Alignment [70.5381163219608]
  We motivate an end-to-end decision-making model based on multimodality-augmented LLM. We propose a reasoning-decision alignment constraint between the paired CoTs and planning results. We dub our proposed large language planners with reasoning-decision alignment as RDA-Driver.
  arXiv  Detail & Related papers  (2024-08-25T16:43:47Z)
• A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences [42.16665455951525]
  The Multi-Objective Vehicle Routing Problem (MOVRP) is a complex optimization problem in the transportation and logistics industry. This paper proposes a novel approach to the MOVRP that aims to create routes that consider drivers' and operators' decisions and preferences. We evaluate two approaches to address this objective: visually attractive route planning and data mining of historical driver behavior to plan similar routes.
  arXiv  Detail & Related papers  (2024-05-25T04:25:00Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Optimizing Inventory Routing: A Decision-Focused Learning Approach using Neural Networks [0.0]
  We formulate and propose a decision-focused learning-based approach to solving real-world IRPs. This approach directly integrates inventory prediction and routing optimization within an end-to-end system potentially ensuring a robust supply chain strategy.
  arXiv  Detail & Related papers  (2023-11-02T04:05:28Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems.
  arXiv  Detail & Related papers  (2023-10-22T02:46:37Z)
• Optimal Sequential Decision-Making in Geosteering: A Reinforcement Learning Approach [0.0]
  Trajectory adjustment decisions throughout the drilling process, called geosteering, affect subsequent choices and information gathering. We use the Deep Q-Network (DQN) method, a model-free reinforcement learning (RL) method that learns directly from the decision environment. For two previously published synthetic geosteering scenarios, our results show that RL achieves high-quality outcomes comparable to the quasi-optimal ADP.
  arXiv  Detail & Related papers  (2023-10-07T10:49:30Z)
• R(Det)^2: Randomized Decision Routing for Object Detection [64.48369663018376]
  We propose a novel approach to combine decision trees and deep neural networks in an end-to-end learning manner for object detection. To facilitate effective learning, we propose randomized decision routing with node selective and associative losses. We name this approach as the randomized decision routing for object detection, abbreviated as R(Det)$2$.
  arXiv  Detail & Related papers  (2022-04-02T07:54:58Z)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  We consider the problem of searching an input maximizing a black-box objective function given a static dataset of input-output queries. A popular approach to solving this problem is maintaining a proxy model that approximates the true objective function. Here, the main challenge is how to avoid adversarially optimized inputs during the search.
  arXiv  Detail & Related papers  (2021-10-27T05:37:12Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  We propose a new algorithm for circuit routing, named Ranking Cost, to form an efficient and trainable router. In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths. Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration.
  arXiv  Detail & Related papers  (2021-10-08T07:22:45Z)
• Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning [52.74071439183113]
  We study the predict-then-optimize framework in the context of sequential decision problems (formulated as MDPs) solved via reinforcement learning. Two significant computational challenges arise in applying decision-focused learning to MDPs.
  arXiv  Detail & Related papers  (2021-06-06T23:53:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.