I am a computer science student and currently working on a Vehicle Routing Problem (VRP) using Particle Swarm Optimization (PSO). I am following the approach outlined in the research paper titled “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem” by The Jin Ai and Voratas Kachitvichyanuku (DOI: https://doi.org/10.1016/j.cie.2008.06.012).

In my implementation, I have modified the solution representation to include pick-up (.1) and drop-off (.2) points. Given a scenario with 7 customers and 3 vehicles, the initial input is a list of randomly assigned numbers to represent the population (e.g., [[[1, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 1, 1, 0, 0, 1], [1, 1, 0, 0, 0, 1, 0, 0]], more particles…]). I have also implemented a function to format the population into a more readable format (e.g., [[{‘1.1’: [datetime.time(0, 15), ‘Depart Location’, PassengerNo, UserID], ‘1.2’: [datetime.time(1, 15), ‘Arrival Location’, PassengerNo, UserID], …}, {…}, {…}]])

Next, I create a customer priority and vehicle priority matrix. The output is as follows:
Customer Priority: [[‘2’, ‘3’, ‘4’, ‘7’, ‘5’, ‘1’, ‘6’]]
Vehicle Priority: [[[2, 1, 0], [0, 1, 2], [1, 0, 2], [0, 1, 2], [0, 1, 2], [1, 0, 2], [0, 1, 2]]]

The customer priority is determined by computing the distance between each customer and the depot, with the nearest customer served first. Each vehicle is then randomly assigned a number based on its latitude and longitude relative to the depot, and the distance between it and the customer is computed to determine the order in which vehicles fetch customers.

When constructing the route, I serve each customer in the priority list, get the vehicle order, and try all possible combinations of customers served by each vehicle. The cost function computes the Euclidean distance between points (e.g., depot to vehicle A to point A back to depot). In the route, the customer is placed in every position, the cost is calculated, and the minimum cost is selected (e.g., [[1,2],[3],[4]], customer 5 will try in the way of [[5,1,2],[1,5,2],[1,2,5]], [[5,3],[3,5]], [[5,4],[4,5]] and select the sequence with least cost.)

However, this approach results in an exponential increase in computation time for a single particle as the number of passengers and vehicles increases. This issue becomes even more pronounced when considering the entire population and multiple iterations to finally display the global best solution.

I am struggling with this concept and urgently need help. Any alternative approaches or ideas to improve the performance of this implementation would be greatly appreciated. Thank you in advance for your assistance.