Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Hybrid Pricing and Cutting Approach for the Multi-Shift Full Truckload Vehicle Routing Problem
91
0
0.0
(
0
)
Added by
Uwe Aickelin
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Full truckload transportation (FTL) in the form of freight containers represents one of the most important transportation modes in international trade. Due to large volume and scale, in FTL, delivery time is often less critical but cost and service quality are crucial. Therefore, efficiently solving large scale multiple shift FTL problems is becoming more and more important and requires further research. In one of our earlier studies, a set covering model and a three-stage solution method were developed for a multi-shift FTL problem. This paper extends the previous work and presents a significantly more efficient approach by hybridising pricing and cutting strategies with metaheuristics (a variable neighbourhood search and a genetic algorithm). The metaheuristics were adopted to find promising columns (vehicle routes) guided by pricing and cuts are dynamically generated to eliminate infeasible flow assignments caused by incompatible commodities. Computational experiments on real-life and artificial benchmark FTL problems showed superior performance both in terms of computational time and solution quality, when compared with previous MIP based three-stage methods and two existing metaheuristics. The proposed cutting and heuristic pricing approach can efficiently solve large scale real-life FTL problems.
rate research
Read More
Quantum annealing (QA) is a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC), and it has shown significant computational advantages in solving combinatorial optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This paper presents a QA approach for solving a variant VRP known as multi-depot capacitated vehicle routing problem (MDCVRP). This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management. We consider heterogeneous depots and vehicles with different capacities. Given a set of heterogeneous depots, the number of vehicles in each depot, heterogeneous depot/vehicle capacities, and a set of spatially distributed customer locations, the MDCVRP attempts to identify routes of various vehicles satisfying the capacity constraints such as that all the customers are served. We model MDCVRP as a quadratic unconstrained binary optimization (QUBO) problem, which minimizes the overall distance traveled by all the vehicles across all depots given the capacity constraints. Furthermore, we formulate a QUBO model for dynamic version of MDCVRP known as D-MDCVRP, which involves dynamic rerouting of vehicles to real-time customer requests. We discuss the problem complexity and a solution approach to solving MDCVRP and D-MDCVRP on quantum annealing hardware from D-Wave.
This paper considers the vehicle routing problem of a fleet operator to serve a set of transportation requests with flexible time windows. That is, the operator presents discounted transportation costs to customers to exchange the time flexibility of pickup or delivery. A win-win routing schedule can be achieved via such a process. Different from previous research, we propose a novel bi-level optimization framework, to fully characterize the interaction and negotiation between the fleet operator and customers. In addition, by utilizing the property of strong duality, and the KKT optimality condition of customer optimization problem, the bi-level vehicle routing problem can be equivalently reformulated as a mixed integer nonlinear programming (MINLP) problem. Besides, an efficient algorithm combining the merits of Lagrangian dual decomposition method and Benders decomposition method, is devised to solve the resultant MINLP problem. Finally, extensive numerical experiments are conducted, which validates the effectiveness of proposed bi-level model on the operation cost saving, and the efficacy of proposed solution algorithm on computation speed.
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve in part because of their large size. We present instances with up to 881 thousand nodes and 383 million edges.
We design a coordination mechanism for truck drivers that uses pricing-and-routing schemes that can help alleviate traffic congestion in a general transportation network. We consider the user heterogeneity in Value-Of-Time (VOT) by adopting a multi-class model with stochastic Origin-Destination (OD) demands for the truck drivers. The main characteristic of the mechanism is that the coordinator asks the truck drivers to declare their desired OD pair and pick their individual VOT from a set of $N$ available options, and guarantees that the resulting pricing-and-routing scheme is Pareto-improving, i.e. every truck driver will be better-off compared to the User Equilibrium (UE) and that every truck driver will have an incentive to truthfully declare his/her VOT, while leading to a revenue-neutral (budget balanced) on average mechanism. This approach enables us to design personalized (VOT-based) pricing-and-routing schemes. We show that the Optimum Pricing Scheme (OPS) can be calculated by solving a nonconvex optimization problem. To improve computational efficiency, we propose an Approximately Optimum Pricing Scheme (AOPS) and prove that it satisfies the aforementioned properties. Both pricing-and-routing schemes are compared to the Congestion Pricing with Uniform Revenue Refunding (CPURR) scheme through extensive simulation experiments where it is shown that OPS and AOPS achieve a much lower expected total travel time and expected total monetary cost for the users compared to the CPURR scheme, without negatively affecting the rest of the network. These results demonstrate the efficiency of personalized (VOT-based) pricing-and-routing schemes.
This paper outlines an exact and a heuristic algorithm for the electric vehicle routing problem with a nonlinear charging function (E-VRP-NL) introduced by Montoya et al. (2017). The E-VRP-NL captures several realistic features of electric vehicles including the battery limited driving range and nonlinear charging process at the charging stations. We formulate this problem as a set-partitioning and solve it using a column generation based algorithm. The resulting pricing problem of the column generation is a complicated problem as, next to the usual operational constraints e.g. time windows and vehicle capacity, electric vehicle related features are also considered. In particular, the nonlinear nature of the battery charging process requires the incorporation of a set of sophisticated recursive functions in the pricing algorithm. We show how these recursive functions allow for the simultaneous evaluation of the routing and charging decisions. Moreover, we illustrate how they can efficiently be embedded in the pricing algorithm. The column generation algorithm is integrated in a branch and bound algorithm and cutting planes are added resulting in a branch-and-price-and-cut algorithm for the E-VRP-NL. Next to the exact algorithm, we also develop a tabu search based heuristic to solve the problem quickly. To prove the efficiency of the proposed algorithms, their performance is tested on benchmark instances from the literature. Our exact algorithm can optimally solve instances with up to 40 customers, including several instances previously unsolved to optimality. The tabu search heuristic proves to be superior to state-of-the-art heuristics in the literature both on solution quality and computation times.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
