اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدVehicle Fleet Sizing, Positioning and Routing Problem with Stochastic Customers
128
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Vehicle Fleet Sizing, Positioning and Routing Problem with Stochastic Customers (VFSPRP-SC) consists on pairing strategic decisions of depot positioning and fleet sizing with operational vehicle routing decisions while taking into account the inherent uncertainty of demand. We successfully solve the VFSPRP-SC with a methodology comprised of two main blocks: i) a scenario generation phase and ii) a two-stage stochastic program. For the first block, a set of scenarios is selected with a simulation-based approach that captures the behavior of the demand and allows us to come up with different solutions that could match different risk profiles. The second block is comprised of a facility location and allocation model and a Multi Depot Vehicle Routing Problem (MDVRP) assembled under a two-stage stochastic program. We propose several novel ideas within our methodology: problem specific cuts that serve as an approximation of the expected second stage costs as a function of first stage decisions; an activation paradigm that guides our main optimization procedure; and, a way of mapping feasible routes from one second-stage problem data into another; among others. We performed experiments for two cases: the first case considers the expected value of the demand, and the second case considers the right tail of the demand distribution, seeking a conservative solution. By using acceleration techniques we obtain solutions within 1 to 6 hours, reasonable times considering the strategic nature of the decision. For the ex-post evaluation, we solve 75% of the instances in less than 3 minutes, meaning that the methodology used to solve the MDVRP is well suited for daily operation.
قيم البحث
اقرأ أيضاً
Given the rise of electric vehicle (EV) adoption, supported by government policies and dropping technology prices, new challenges arise in the modeling and operation of electric transportation. In this paper, we present a model for solving the EV rou
ting problem while accounting for real-life stochastic demand behavior. We present a mathematical formulation that minimizes travel time and energy costs of an EV fleet. The EV is represented by a battery energy consumption model. To adapt our formulation to real-life scenarios, customer pick-ups and drop-offs were modeled as stochastic parameters. A chance-constrained optimization model is proposed for addressing pick-ups and drop-offs uncertainties. Computational validation of the model is provided based on representative transportation scenarios. Results obtained showed a quick convergence of our model with verifiable solutions. Finally, the impact of electric vehicles charging is validated in Downtown Manhattan, New York by assessing the effect on the distribution grid.
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 p
roblems (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 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 i
ncluding 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.
We consider the non-stationary stochastic lot sizing problem with backorder costs and make a cost comparison among different lot-sizing strategies. We initially provide an overview of the strategies and some corresponding solution approaches in the l
iterature. We then compare the cost performances of the lot-sizing strategies on a common test bed while taking into account the added value of realized demand information. The results of this numerical experience enable us to derive novel insights about the cost performance of different stochastic lot-sizing strategies under re-planning with respect to demand realization.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
