Review on Efficient Multi-Objective Optimization for the Vehicle Routing Problem with Time Window to Enhance Resilience

Abstract

The Vehicle Routing Problem under time window uncertainty A new type of travel time disturbance is constructed to capture the characteristics of the life scenario, and its disturbance region is determined by the maximum disturbance degree Two objectives are defined to minimise the total distance and the number of vehicles An advanced Robust Multi Objective Particle Swarm Optimization approach is developed using advanced coding, decoding model, reliability metrics and local search strategies to identify optimal solutions Due to the particles in the decision space, the properties of the problem space are fully exploited to drive the robust optimization, while the proposed metric measures the robustness of the solutions during the process Further improvements are achieved by problem based local search and route based local search strategies Several robust optimization benchmarks, where perturbations are applied to selected problems, demonstrate that our proposed algorithm can generate sufficiently robust solutions and ensure their optimality.

Introduction

I. INTRODUCTION

The VRPTW is a typical optimisation issue that arises in a variety of real-world applications such as logistics, transportation, and distribution. VRPTW's purpose is to find the best set of routes for a fleet of vehicles serving a specified customer group in a given period of time while minimising total distance travelled, travel time, and vehicle count. The problem is NP-hard and has been studied extensively in the literature. In recent years, researchers have focused on developing multi-objective optimization techniques to address the limitations of traditional VRPTW models, which often optimise a single objective function. Multi-objective optimization aims to optimise multiple targets simultaneously, providing a more comprehensive and effective solution. In particular, powerful multi-objective optimization seeks to optimise objectives while taking into account the uncertainty and variability of the problem parameters. To solve the VRPTW problem, we suggest a sophisticated multi-objective optimisation method that minimises the total distance travelled, the time required, and the number of vehicles needed. The proposed method takes into account the uncertainty related to travel time, demand and the number of available vehicles.

This article's goal is to propose a powerful multi-objective optimisation strategy to the vehicle Routing Problem with Windows of Time. VRPTW is a well-known combinatorial optimisation problem that seeks the best set of routes for a fleet of vehicles in order to serve a group of clients in a certain time period while minimising total travel distance. or the number of vehicles on the road. VRPTW has many real-world applications, including transportation and logistics, food delivery, waste management, and more. The problem is difficult due to its combinatorial nature and the presence of time constraints. In addition, real-world problems are often uncertain and intermittent, such as traffic jams, vehicle breakdowns, or unexpected fluctuations in demand. Therefore, it is important to develop robust optimization methods capable of handling such uncertainties to ensure the feasibility and effectiveness of solutions. The proposed method aims to solve the limitations of traditional deterministic optimization methods by considering the uncertainty and reliability of the solutions. The article has designed VRPTW as a multi-objective optimisation problem, with the aims of minimising overall distance driven, vehicle number used, and departure from the expected timetable.

Vehicle routing problems with Windows Time (VRPTW) and difficulties in resolving them under uncertain conditions. He emphasised the importance of VRPTW in real-world applications and noted that current algorithms for solving VRPTW assume that demand and travel time are known with certainty, but in reality are not. . It must be. always true in practice. a new algorithm called R-MOPSO with PBLS can generate solutions against uncertainty.

The introduction also describes the related work in the field, the limitations of the existing methods, and the contributions of the paper, including the formulation of new problems,. design new algorithms and evaluate tests with profound experience. Overall, the introduction sets the stage for understanding why the research is important and what makes it so new.

II. LITERATURE REVIEW

[1]. The proposed model is to use a heuristic algorithm called deterministic annealing to solve the Windows Time-Based Media Routing Problem (VRPTW).Each customer is initially assigned to a different car, and after that, the programme uses a local search method to find a better option.

Algorithm then calculates the temperature and cooling schedule for the annealing process, which involves changing the solution multiple times and accepting new solutions with a certain probability depending on the temperature.

During incubation, the algorithm uses a set of moves that involve exchanging customers between routes or inserting them into existing routes. The motions aim to retain the solution's feasibility while enhancing its quality. In order to explore diverse areas of the search space and prevent being trapped in the local optimum zone, the algorithm additionally incorporates a number of neighbourhood structures.

A set of benchmark versions were used to assess the method discussed in this article and to compare it to other contemporary techniques. The outcomes demonstrate that the algorithm can produce high-quality answers in a short amount of time, making it a promising approach to solving VRPTW.

[2]. The proposed system addresses the Electric Vehicle (EV) coordination problem, which involves deciding on the optimal charging and battery swapping options for multiple EVs within a given time window. To solve this problem, the system constructs a mixed integer programming model that considers several charging options, such as partial charging and battery swapping.

To address this issue, the research suggests an enhanced ACO algorithm. To increase effectiveness in choosing which clients to visit, the ACO algorithm is paired with an improved insertion experience and local search techniques. This approach helps to find the optimal route for EVs to travel while minimising the total travel time and charging cost.

The research suggests a probabilistic selection model that combines the impacts of distance and time frame in order to further increase search efficiency.

The ACO algorithm incorporates this model to effectively choose the visitors. Based on the pheromone trail and heuristic data, the ACO algorithm utilises a probabilistic method to choose the next node to visit.

 Conducting computational tests on the dataset presented by Schneider et al. is the last phase of the suggested system. The outcomes demonstrate how well the enhanced ant colony algorithm handles this issue. In comparison to other cutting-edge algorithms, the suggested system performed better in terms of solution quality and computational time.

In summary, the suggested method offers a solution to the EV coordination problem that considers multiple charging options and time windows. It provides an efficient way to optimise the EVs' routes and charging schedules, ultimately reducing the total charging cost and travel time. The improved ACO algorithm, along with the probabilistic selection model, demonstrates better performance than existing methods, making it a promising approach to tackle this problem.

[3]. The article proposes a method to optimise the routing of delivery trucks for an e-commerce company. The authors divided the method into two steps to reduce the size of the model. In step 1, the authors collected store coordinates on a map using the store address and Google API in Python. They also collected demand data from historical transaction data between fulfilment centres and stores.

In step 2, the authors configured the distance matrix and travel time matrix for the trucks in the cluster using Google API with Python. The shipping cost matrix was derived from the distance matrix multiplied by the unit shipping cost. To accommodate ordering requirements, VRP with time window (VRPTW) was applied to account for upper and lower time limits, as well as vehicle capacity limits. The authors proposed a mathematical model to find the optimal set of routes with a minimum total cost while satisfying these constraints.

The proposed method utilises advanced technologies to collect and process data. Using Google API with Python to collect store coordinates and calculate the distance and travel time matrix saves time and effort compared to manual collection. This approach also allows for accurate and up-to-date data collection, which is crucial for an effective delivery routing system.

Applying VRPTW is also an important feature of this method. This allows the algorithm to consider time windows and vehicle capacity limits when generating the optimal set of routes. This ensures that the algorithm generates practical solutions that consider real-world constraints.

The proposed mathematical model aims to minimise the total cost of shipping while satisfying the constraints mentioned above. This model considers the distance matrix, travel time matrix, and shipping cost matrix, which are all crucial factors in determining the total cost. The model also considers vehicle capacity and time windows to generate feasible solutions.

Overall, the proposed method offers a practical and efficient solution for optimising the routing of delivery trucks for e-commerce companies. The method utilises advanced technologies to collect and process data and considers real-world constraints to generate feasible solutions.

[4]. The two-step multi-objective evolution technique (TS-MOEA) is used to solve the MO-MDVRPTW multi-target media routing issue. This task tries to reduce certain targets, such as total distance travelled and vehicle count, while optimising the routing of cars from multiple depots in order to best service a group of clients with a time lag.

Utilisation ease and overall wait duration. The primary objective of the algorithm's first step is to identify extreme solutions that roughly form a Pareto front.

This is accomplished using a tournament selection procedure and a local search operator that looks for solutions in the area. After ideas are evaluated based on how dominant they are, non-dominant solutions are chosen for Phase II. The extreme solutions discovered in Phase II are expanded to cover the whole Pareto front. In order to do this, the crossover operator, which creates sub-solutions by combining the two root solutions, and the mutation operator, which adds random modifications to each solution, are used.

Then, if top-down approaches fail to succeed, they are assessed and added to the population. The two-step approach provides a fresh technique to strike a balance between convergence and variety. The algorithm can reach promising areas of the Pareto front rapidly by concentrating on extreme phase I solutions. These answers can be carried over to phase II, allowing the algorithm to investigate a wider range of Pareto front areas.

[5]. A complete and practical solution is needed for the complicated Skill Vehicle Routing Problem (Skill VRP) with dynamic timing and servicing time windows. The authors offer a solution to this problem in this regard that is multi-step in nature.

The suggested method's initial stage is problem formulation. The authors define the Skill VRP in this stage, which entails a fleet of skilled vehicles that can serve a number of clients within predetermined time frames. The variable service time at each customer's location, which is based on the vehicle's technological capability, is another factor taken into account by the writers. The expense of operating the vehicle is also time- and skill-dependent.

This approach to problem formulation is crucial because it makes it easier to comprehend the complexity of the issue and the factors that must be taken into account while finding a solution.

The second phase is creating a Mixed Integer Linear Programming (MILP) model that accounts for both scheduling and vehicle routing choices.

This model is a thorough and effective method for resolving the Skill VRP since it takes into account the dynamic service time as well as time- and skill-dependent expenses. This stage is essential for ensuring that the variables taken into account are extensive and that the model generated can manage the complexity of the issue.

The CPLEX solver, a popular optimisation tool in both business and academia, is utilised by the authors to solve the MILP model in the third stage. This guarantees that the answer is the best one and that it can be used in actual situations. A strong tool for effectively resolving complex optimisation issues is the CPLEX solver.

The fourth phase entails running a computer test on a number of reference versions to gauge how successful the suggested approach is. In order to test the effectiveness of their suggested strategy objectively, the authors compare their findings to those of other strategies that have been used in the literature. This phase is extremely important since it enables comparison of the proposed method's performance to other techniques already in use in the literature.

The authors investigate the experimental data gleaned from the computer test in the final phase, the fifth, in order to assess the viability of their suggested approach.

They include details on how their technique performs in various parameter settings and issue scenarios, which might be helpful to practitioners in the logistics and transportation management industries. This phase is essential to ensuring that the suggested approach can be applied to solve practical issues and offer guidance to experts in the subject.

The suggested method for the Skill VRP is efficient and takes the intricacy of the issue into account. The CPLEX solver and MILP models provide ideal and useful outcomes. For practitioners in logistics and transportation management, the authors' analysis provides insightful information. This is a huge development for the industry.

III. CONSOLIDATED TABLE

IV. ACKNOWLEDGEMENT

A person's success cannot be entirely credited to their own efforts alone; it also depends on the advice, support, and collaboration of mentors, elders, and friends. We wish to thank Dr. Praveen Kumar K V, Professor in the Department of Computer Science and Engineering at Sapthagiri College of Engineering, and Dr. Kamalakshi Naganna, Professor and Head of the Department of Computer Science and Engineering at Sapthagiri College of Engineering, for their constant support, guidance, and assistance throughout our work. We also thank our parents and friends for being there for us emotionally.

Conclusion

The Paper proposes R-MOPSO with PBLS as an effective algorithm for solving the VRPTW problem under uncertainty. Sensitivity analysis shows that increasing population size and iterations improves solution quality, but increasing objectives negatively impacts efficiency. Overall, the paper contributes to the field by proposing a new algorithm and demonstrating its effectiveness through experiments. One area for future enhancement is to improve the algorithm\'s performance on larger instances or with more objectives. The Paper suggests that this could be achieved by developing more efficient search strategies or by parallelizing the algorithm to take advantage of modern computing architectures. Another area for future enhancement is to investigate the use of other metaheuristic algorithms or hybrid approaches that combine multiple algorithms. This could potentially lead to better performance on certain types of instances or under different levels of uncertainty.

References

[1] M. Baranwal, P. M. Parekh, L. Marla, S. M. Salapaka and C. L. Beck, \"Vehicle Routing Problem with Time Windows: A Deterministic Annealing approach,\" 2016 American Control Conference (ACC), Boston, MA, USA, 2016, pp. 790-795, doi: 10.1109/ACC.2016.7525010. [2] H. Mao, J. Shi, Y. Zhou and G. Zhang, \"The Electric Vehicle Routing Problem With Time Windows and Multiple Recharging Options,\" in IEEE Access, vol. 8, pp. 114864-114875, 2020, doi: 10.1109/ACCESS.2020.3003000. [3] P. T. Anh, C. Tuan Cuong and P. N. Ky Phuc, \"The vehicle routing problem with time windows: A case study of fresh food distribution center,\" 2019 11th International Conference on Knowledge and Systems Engineering (KSE), Da Nang, Vietnam, 2019, pp. 1-5, doi: 10.1109/KSE.2019.8919443. [4] J. Wang, T. Weng and Q. Zhang, \"A Two-Stage Multiobjective Evolutionary Algorithm for Multiobjective Multi depot Vehicle Routing Problem With Time Windows,\" in IEEE Transactions on Cybernetics, vol. 49, no. 7, pp. 2467-2478, July 2019, doi: 10.1109/TCYB.2018.2821180. [5] X. Yan, B. Xiao, Y. Xiao, Z. Zhao, L. Ma and N. Wang, \"Skill Vehicle Routing Problem With Time Windows Considering Dynamic Service Times and Time-Skill-Dependent Costs,\" in IEEE Access, vol. 7, pp. 77208-77221, 2019, doi: 10.1109/ACCESS.2019.2919963.

Copyright

Copyright © 2023 Mayank Raj, Dr. Praveen Kumar K V. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.