ترغب بنشر مسار تعليمي؟ اضغط هنا

Vehicle Routing Problem with Flexible Time Window: A Bi-level Approach

119   0   0.0 ( 0 )
 نشر من قبل Canqi Yao
 تاريخ النشر 2021
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

164 - Yang Li , Meng Han , Zhen Yang 2021
A community integrated energy system (CIES) with an electric vehicle charging station (EVCS) provides a new way for tackling growing concerns of energy efficiency and environmental pollution, it is a critical task to coordinate flexible demand respon se and multiple renewable uncertainties. To this end, a novel bi-level optimal dispatching model for the CIES with an EVCS in multi-stakeholder scenarios is established in this paper. In this model, an integrated demand response program is designed to promote a balance between energy supply and demand while maintaining a user comprehensive satisfaction within an acceptable range. To further tap the potential of demand response through flexibly guiding users energy consumption and electric vehicles behaviors (charging, discharging and providing spinning reserves), a dynamic pricing mechanism combining time-of-use and real-time pricing is put forward. In the solution phase, by using sequence operation theory (SOT), the original chance-constrained programming (CCP) model is converted into a readily solvable mixed-integer linear programming (MILP) formulation and finally solved by CPLEX solver. The simulation results on a practical CIES located in North China demonstrate that the presented method manages to balance the interests between CIES and EVCS via the coordination of flexible demand response and uncertain renewables.
Lithium-ion battery packs are usually composed of hundreds of cells arranged in series and parallel connections. The proper functioning of these complex devices requires suitable Battery Management Systems (BMSs). Advanced BMSs rely on mathematical m odels to assure safety and high performance. While many approaches have been proposed for the management of single cells, the control of multiple cells has been less investigated and usually relies on simplified models such as equivalent circuit models. This paper addresses the management of a battery pack in which each cell is explicitly modelled as the Single Particle Model with electrolyte and thermal dynamics. A nonlinear Model Predictive Control (MPC) is presented for optimally charging the battery pack while taking voltage and temperature limits on each cell into account. Since the computational cost of nonlinear MPC grows significantly with the complexity of the underlying model, a sensitivity-based MPC (sMPC) is proposed, in which the model adopted is obtained by linearizing the dynamics along a nominal trajectory that is updated over time. The resulting sMPC optimizations are quadratic programs which can be solved in real-time even for large battery packs (e.g. fully electric motorbike with 156 cells) while achieving the same performance of the nonlinear MPC.
Unsignalized intersection cooperation of connected and automated vehicles (CAVs) is able to eliminate green time loss of signalized intersections and improve traffic efficiency. Most of the existing research on unsignalized intersection cooperation c onsiders fixed lane direction, where only specific turning behavior of vehicles is allowed on each lane. Given that traffic volume and the proportion of vehicles with different turning expectation may change with time, fixed lane direction may lead to inefficiency at intersections. This paper proposes a multi-lane unsignalized intersection cooperation method that considers flexible lane direction. The two-dimensional distribution of vehicles is calculated and vehicles that are not in conflict are scheduled to pass the intersection simultaneously. The formation reconfiguration method is utilized to achieve collision-free longitudinal and lateral position adjustment of vehicles. Simulations are conducted at different input traffic volumes and turning proportion of incoming vehicles, and the results indicate that our method outperformances the fixed-lane-direction unsignalized cooperation method and the signalized method.
127 - Hui Song , Chen Liu , Mahdi Jalili 2021
The increased uptake of electric vehicles (EVs) leads to increased demand for electricity, and sometime pressure to power grids. Uncoordinated charging of EVs may result in putting pressure on distribution networks, and often some form of optimisatio n is required in the charging process. Optimal coordinated charging is a multi-objective optimisation problem in nature, with objective functions such as minimum price charging and minimum disruptions to the grid. In this manuscript, we propose a general multi-objective EV charging/discharging schedule (MOEVCS) framework, where the time of use (TOU) tariff is designed according to the load request at each time stamp. To obtain the optimal scheduling scheme and balance the competing benefits from different stakeholders, such as EV owners, EV charging stations (EVCS), and the grid operator, we design three conflicting objective functions including EV owner cost, EVCS profit, and the network impact. Moreover, we create four application scenarios with different charging request distributions over the investigated periods. We use a constraint multi-objective evolutionary algorithm (MOEA) to solve the problem. Our results demonstrate the effectiveness of MOEVCS in making a balance between three conflicting objectives.
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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا