A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences
- URL: http://arxiv.org/abs/2405.16051v1
- Date: Sat, 25 May 2024 04:25:00 GMT
- Title: A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences
- Authors: Juan Pablo Mesa, Alejandro Montoya, Raul Ramos-Pollán, Mauricio Toro,
- Abstract summary: 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.
- Score: 42.16665455951525
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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. Using a real-world dataset provided by Amazon, we demonstrate that data mining of historical patterns is more effective than visual attractiveness metrics found in the literature. Furthermore, we propose a bi-objective problem to balance the similarity of routes to historical routes and minimize routing costs. We propose a two-stage GRASP algorithm with heuristic box splitting to solve this problem. The proposed algorithm aims to approximate the Pareto front and to present routes that cover a wide range of the objective function space. The results demonstrate that our approach can generate a small number of non-dominated solutions per instance, which can help decision-makers to identify trade-offs between routing costs and drivers' preferences. Our approach has the potential to enhance the last-mile delivery operations of logistics companies by balancing these conflicting objectives.
Related papers
- 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) - Inverse Optimization for Routing Problems [3.282021317933024]
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.
arXiv Detail & Related papers (2023-07-14T14:03:47Z) - 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) - Preference-Aware Delivery Planning for Last-Mile Logistics [3.04585143845864]
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.
arXiv Detail & Related papers (2023-03-08T02:10:59Z) - RSG-Net: Towards Rich Sematic Relationship Prediction for Intelligent
Vehicle in Complex Environments [72.04891523115535]
We propose RSG-Net (Road Scene Graph Net): a graph convolutional network designed to predict potential semantic relationships from object proposals.
The experimental results indicate that this network, trained on Road Scene Graph dataset, could efficiently predict potential semantic relationships among objects around the ego-vehicle.
arXiv Detail & Related papers (2022-07-16T12:40:17Z) - Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2
Benchmark [133.46066694893318]
We evaluate the performance of neural network-based solvers for optimal transport.
We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
arXiv Detail & Related papers (2021-06-03T15:59:28Z) - Divide-and-Conquer for Lane-Aware Diverse Trajectory Prediction [71.97877759413272]
Trajectory prediction is a safety-critical tool for autonomous vehicles to plan and execute actions.
Recent methods have achieved strong performances using Multi-Choice Learning objectives like winner-takes-all (WTA) or best-of-many.
Our work addresses two key challenges in trajectory prediction, learning outputs, and better predictions by imposing constraints using driving knowledge.
arXiv Detail & Related papers (2021-04-16T17:58:56Z) - End-to-end Interpretable Neural Motion Planner [78.69295676456085]
We propose a neural motion planner (NMP) for learning to drive autonomously in complex urban scenarios.
We design a holistic model that takes as input raw LIDAR data and a HD map and produces interpretable intermediate representations.
We demonstrate the effectiveness of our approach in real-world driving data captured in several cities in North America.
arXiv Detail & Related papers (2021-01-17T14:16: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) - Improving Movement Predictions of Traffic Actors in Bird's-Eye View
Models using GANs and Differentiable Trajectory Rasterization [12.652210024012374]
One of the most critical pieces of the self-driving puzzle is the task of predicting future movement of surrounding traffic actors.
Methods based on top-down sceneization on one side and Generative Adrial Networks (GANs) on the other have shown to be particularly successful.
In this paper we build upon these two directions and propose aversa-based conditional GAN architecture.
We evaluate the proposed method on a large-scale, real-world data set, showing that it outperforms state-of-the-art GAN-based baselines.
arXiv Detail & Related papers (2020-04-14T00:41:17Z)
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.