A Branch-Cut-and-Price Approach for the Single-Trip and Multi-Trip Two-Echelon Vehicle Routing Problem with Time Windows

Transportation Science, Год журнала: 2022, Номер 56(6), С. 1598 - 1617

Опубликована: Март 14, 2022

The paper studies the two-echelon capacitated vehicle routing problem with time windows, in which delivery of freight from depots to customers is performed using intermediate facilities called satellites. We consider variant precedence constraints for unloading and loading at In this allows storage consolidation Thus, total transportation cost may decrease comparison alternative exact synchronization suggest a mixed integer programming formulation an exponential number route variables that link first-echelon second-echelon routes. Routes second echelon connecting satellites clients consist multiple trips visit several A branch-cut-and-price algorithm proposed solve efficiently problem. This first literature multi-trip also present postprocessing procedure check whether solution can be transformed avoid without increasing its cost. It shown all single-trip instances solved optimality admit optimal solutions same both variants either or constraints. Experimental results reveal our used these significantly faster than another recent approach literature.

Язык: Английский

---

Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window

ACM Transactions on Intelligent Systems and Technology, Год журнала: 2024, Номер 15(2), С. 1 - 19

Опубликована: Янв. 25, 2024

Vehicle routing problem with time window (VRPTW) is of great importance for a wide spectrum services and real-life applications, such as online take-out car-hailing platforms. A promising method should generate high-qualified solutions within limited inference time, there are three major challenges: (a) directly optimizing the goal several practical constraints; (b) efficiently handling individual time-window limits; (c) modeling cooperation among vehicle fleet. In this article, we present an end-to-end reinforcement learning framework to solve VRPTW. First, propose agent model that encodes constraints into features input conducts harsh policy on output when generating deterministic results. Second, design penalty augmented reward limits during gradient propagation. Third, task handler enable different vehicles. We perform extensive experiments two real-world datasets one public benchmark dataset. Results demonstrate our solution improves performance by up 11.7% compared other RL baselines could instances seconds, while existing heuristic take minutes well maintain quality solutions. Moreover, thoroughly analyzed meaningful implications due real-time response ability.

Язык: Английский

---

A machine learning-based branch and price algorithm for a sampled vehicle routing problem

OR Spectrum, Год журнала: 2021, Номер 43(3), С. 693 - 732

Опубликована: Янв. 30, 2021

Abstract Planning of operations, such as routing vehicles, is often performed repetitively in rea-world settings, either by humans or algorithms solving mathematical problems. While build experience over multiple executions planning tasks and are able to recognize common patterns different problem instances, classical optimization solve every instance independently. Machine learning (ML) can be seen a computational counterpart the human ability based on experience. We consider variants Vehicle Routing Problem with Time Windows Capacitated Problem, which assumption that instances follow specific patterns. For this problem, we propose ML-based branch price framework explicitly utilizes those In context, ML models used two ways: (a) predict value binary decision variables optimal solution (b) branching scores for fractional full strong branching. The prediction then integrated node selection policy, while predicted score within variable policy. These approaches reliability-based algorithm assesses their quality allows replacing other (classical) better performing at level each instance. Computational results show our outperform benchmark strategies. Further, demonstrate approach robust respect small changes sizes.

Язык: Английский

---

Arc flow formulations based on dynamic programming: Theoretical foundations and applications

European Journal of Operational Research, Год журнала: 2021, Номер 296(1), С. 3 - 21

Опубликована: Апрель 24, 2021

Язык: Английский

---

Vehicle routing with cumulative objectives: A state of the art and analysis

Computers & Industrial Engineering, Год журнала: 2022, Номер 169, С. 108054 - 108054

Опубликована: Март 5, 2022

In the past decades, there has been an increasing body of research in vehicle routing problems involving cumulative costs. These consider objective functions such as sum arrival times to customers or costs based on vehicles' load throughout routes. This paper reviews this type problem by means (Cum-VRP) and capacitated (CCVRP). doing so, we present discuss all related variants with regard different features proposed over time. Moreover, provide analysis papers concerning solution algorithms used benchmark instances. Finally, overview trends promising areas for further are also provided.

Язык: Английский

---

RBG: Hierarchically Solving Large-Scale Routing Problems in Logistic Systems via Reinforcement Learning

Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Год журнала: 2022, Номер unknown, С. 4648 - 4658

Опубликована: Авг. 12, 2022

The large-scale vehicle routing problems (VRPs) are defined based on the classical VRPs with thousands of customers. It is an important optimization problem in modern logistic systems, since efficiently obtaining high-quality solutions can greatly reduce operation expenses as well improve customer satisfaction. Most existing algorithms, including traditional non-learning heuristics and learning-based methods, only perform small-scale instances usually no more than hundreds In this paper we present a novel Rewriting-by-Generating (RBG) framework which solves hierarchically. RBG consists rewriter agent that refines division globally elementary generator to infer regional locally. also flexible multiple CVRP variant could be continuously evolved up-to-date designs. We conduct extensive experiments both synthetic real-world data demonstrate effectiveness efficiency our proposed framework. outperforms HGS, one best heuristic method for CVRPs shortens inference time. Online evaluation conducted deployed express platform Guangdong, China, where shows advantages other alternative built-in algorithms.

Язык: Английский

---

A Numerically Exact Algorithm for the Bin-Packing Problem

INFORMS journal on computing, Год журнала: 2024, Номер 36(1), С. 141 - 162

Опубликована: Янв. 1, 2024

We propose a numerically exact algorithm for solving the Bin-Packing Problem (BPP) based on branch-price-and-cut framework combined with pattern-enumeration method. Key to is novel technique computation of safe dual bounds widely adopted set covering reformulation BPP (tightened additional valid inequalities) precision that higher than one general-purpose floating-point solvers. Our also relies an integer (fixed-point) label setting pricing problem associated tightened set-covering formulation. To best our knowledge, ours first and practical large-scale instances. Extensive computational results instances affected by notorious numerical difficulties (those Augmented Non-IRUP class) show outperforms all not state-of-the-art algorithms branch-and-cut-and-price techniques rely formulation BPP. History: Accepted Andrea Lodi, Area Editor Design & Analysis Algorithms − Discrete.

Язык: Английский

---

Research trends in combinatorial optimization

International Transactions in Operational Research, Год журнала: 2021, Номер 29(2), С. 667 - 705

Опубликована: Май 27, 2021

Abstract Real‐world problems are becoming highly complex and therefore have to be solved with combinatorial optimization (CO) techniques. Motivated by the strong increase in publications on CO, 8393 articles from this research field subjected a bibliometric analysis. The corpus of literature is examined using mathematical methods novel algorithm for keyword In addition most relevant countries, organizations, authors as well their collaborations, pertinent CO problems, solution methods, application areas presented. Publications focus mainly development or enhancement metaheuristics like genetic algorithms. increasingly problem‐oriented studies deal particularly real‐world applications within energy sector, production data management, which increasing relevance due various global developments. demonstration trends can support researchers identifying issues regarding expanding transforming area.

Язык: Английский

---

Multi-shuttle crane scheduling in automated storage and retrieval systems

European Journal of Operational Research, Год журнала: 2022, Номер 302(3), С. 892 - 908

Опубликована: Фев. 2, 2022

Язык: Английский

---

Enhancing travel time prediction with deep learning on chronological and retrospective time order information of big traffic data

Annals of Operations Research, Год журнала: 2023, Номер 343(3), С. 1095 - 1128

Опубликована: Апрель 6, 2023

Язык: Английский

---