Preference-Aware Delivery Planning for Last-Mile Logistics
- URL: http://arxiv.org/abs/2303.04333v1
- Date: Wed, 8 Mar 2023 02:10:59 GMT
- Title: Preference-Aware Delivery Planning for Last-Mile Logistics
- Authors: Qian Shao, Shih-Fen Cheng
- Abstract summary: We propose a novel hierarchical route with learnable parameters that combines the strength of both the optimization and machine learning approaches.
By using a real-world delivery dataset provided by the Amazon Last Mile Research Challenge, we demonstrate the importance of having both the optimization and the machine learning components.
- Score: 3.04585143845864
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimizing delivery routes for last-mile logistics service is challenging and
has attracted the attention of many researchers. These problems are usually
modeled and solved as variants of vehicle routing problems (VRPs) with
challenging real-world constraints (e.g., time windows, precedence). However,
despite many decades of solid research on solving these VRP instances, we still
see significant gaps between optimized routes and the routes that are actually
preferred by the practitioners. Most of these gaps are due to the difference
between what's being optimized, and what the practitioners actually care about,
which is hard to be defined exactly in many instances. In this paper, we
propose a novel hierarchical route optimizer with learnable parameters that
combines the strength of both the optimization and machine learning approaches.
Our hierarchical router first solves a zone-level Traveling Salesman Problem
with learnable weights on various zone-level features; with the zone visit
sequence fixed, we then solve the stop-level vehicle routing problem as a
Shortest Hamiltonian Path problem. The Bayesian optimization approach is then
introduced to allow us to adjust the weights to be assigned to different zone
features used in solving the zone-level Traveling Salesman Problem. By using a
real-world delivery dataset provided by the Amazon Last Mile Routing Research
Challenge, we demonstrate the importance of having both the optimization and
the machine learning components. We also demonstrate how we can use
route-related features to identify instances that we might have difficulty
with. This paves ways to further research on how we can tackle these difficult
instances.
Related papers
- RouteFinder: Towards Foundation Models for Vehicle Routing Problems [18.158173261177186]
Vehicle Routing Problems (VRPs) are optimization problems with significant real-world implications.
Despite the recent progress made in learning to solve individual VRP variants, there is a lack of a unified approach.
This paper introduces RouteFinder, a framework for developing foundation models for VRPs.
arXiv Detail & Related papers (2024-06-21T09:34:26Z) - LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
Path planning is a fundamental scientific problem in robotics and autonomous navigation.
Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows.
We propose a new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs.
This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios.
arXiv Detail & Related papers (2024-06-20T01:24:30Z) - 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) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts.
We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances.
We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
arXiv Detail & Related papers (2023-04-28T07:09:23Z) - Combinatorial Optimization enriched Machine Learning to solve the
Dynamic Vehicle Routing Problem with Time Windows [5.4807970361321585]
We propose a novel machine learning pipeline that incorporates an optimization layer.
We apply this pipeline to a dynamic vehicle routing problem with waves, which was recently promoted in the EURO Meets NeurIPS Competition at NeurIPS 2022.
Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem.
arXiv Detail & Related papers (2023-04-03T08:23:09Z) - Efficient Online Reinforcement Learning with Offline Data [78.92501185886569]
We show that we can simply apply existing off-policy methods to leverage offline data when learning online.
We extensively ablate these design choices, demonstrating the key factors that most affect performance.
We see that correct application of these simple recommendations can provide a $mathbf2.5times$ improvement over existing approaches.
arXiv Detail & Related papers (2023-02-06T17:30:22Z) - 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) - Detecting 32 Pedestrian Attributes for Autonomous Vehicles [103.87351701138554]
In this paper, we address the problem of jointly detecting pedestrians and recognizing 32 pedestrian attributes.
We introduce a Multi-Task Learning (MTL) model relying on a composite field framework, which achieves both goals in an efficient way.
We show competitive detection and attribute recognition results, as well as a more stable MTL training.
arXiv Detail & Related papers (2020-12-04T15:10:12Z) - Scalable Many-Objective Pathfinding Benchmark Suite [0.0]
We propose a scalable many-objective benchmark problem covering most of the important features for routing applications based on real-world data.
We define five objective functions representing distance, traveling time, delays caused by accidents, and two route specific features such as curvature and elevation.
Since this test benchmark can be easily transferred to real-world routing problems, we construct a routing problem from OpenStreetMap data.
arXiv Detail & Related papers (2020-10-09T11:17:49Z) - Learning to Solve Vehicle Routing Problems with Time Windows through
Joint Attention [6.155158115218501]
We develop a policy model that is able to start and extend multiple routes concurrently by using attention on the joint action space of several tours.
In comprehensive experiments on three variants of the vehicle routing problem with time windows we show that our model called JAMPR works well for different problem sizes and outperforms the existing state-of-the-art constructive model.
arXiv Detail & Related papers (2020-06-16T12:08:10Z)
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.