rajah
Reputation: 21
IndexError: list index out of range when executing _get_start_solution in vehicle routing problem
I’m working on a vehicle routing problem implementation, and I’m encountering an IndexError when executing the _get_start_solution function. The error occurs during the final print statement of the solution.
Details:
'Traceback (most recent call last):
File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\test_alpha_gamma.py", line 128, in <module>
main()
File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\test_alpha_gamma.py", line 124, in main
test(epsilon, gamma, alpha)
File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\test_alpha_gamma.py", line 96, in test
solution = alg.solve(problem, start_time,type="eps_greedy", method="TS",eps=epsilon, ensemble=[])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\algorithm.py", line 704, in solve
start_solution = self._get_start_solution(problem)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\algorithm.py", line 802, in _get_start_solution
f"Final solution: {solution.routes}, "
File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\solution.py", line 391, in __repr__
self.earliest[i],
~~~~~~~~~~~~~^^^
IndexError: list index out of range'
I have 30 clients in my instance, but it seems that one of the indices is going out of range. The traceback indicates that the error arises when attempting to access the routes after minimizing the vehicles.
Here’s a snippet of my _get_start_solution function for context:
def _get_start_solution(self, problem):
"""
Generate an initial solution for the problem by assigning requests to vehicles
based on vehicle capacity and customer demands.
Parameters
----------
problem : `Problem`
The optimization problem containing vehicles and requests.
Returns
-------
solution : `Solution`
The initial solution object with routes for all vehicles.
"""
# Initialize the solution object
solution = Solution(problem)
num_customers = len(problem.P) # Number of customers (pickup points)
print(f"Number of customers: {num_customers}")
# Default vehicle capacity, adjust if capacity is stored elsewhere in problem
vehicle_capacity = getattr(problem.vehicles[0], 'capacity', 100) # Get vehicle capacity from the first vehicle
print(f"Vehicle capacity: {vehicle_capacity}")
# Initialize routes and remaining capacities for each vehicle
routes = []
capacities = []
vehicle_id = 0 # Start vehicle IDs from 0
# Create a list of customers (excluding depot which is assumed to be customer 0)
customers = list(range(1, num_customers + 1)) # Only customers, not the depot
print(f"Shuffling customers: {customers}")
random.shuffle(customers)
# Create a new route whenever the vehicle is full
current_route = []
current_capacity = vehicle_capacity
# Iterate over the shuffled customers and assign them to vehicles
for customer_id in customers:
if customer_id not in problem.P:
print(f"Customer {customer_id} not found in problem.P")
continue # Skip this customer if they do not exist
# Get the demand of the customer (assuming demand is stored in 'load')
demand = problem.P[customer_id].load # Adjust if demand attribute is different
print(f"Customer {customer_id} demand: {demand}")
# Check if the current vehicle can accommodate the customer's demand
if current_capacity >= demand:
current_route.append(customer_id)
current_capacity -= demand
# Remove the customer from the request bank as it is now assigned
if customer_id in solution.request_bank:
solution.request_bank.remove(customer_id)
else:
# If the current vehicle is full, finalize the current route and start a new one
if current_route: # Only append if current_route is not empty
route = Route(problem, vehicle_id)
route.route = current_route # Assign the customers to the route
routes.append(route) # Add the completed route to the routes list
# Start a new route with a new vehicle
current_route = [customer_id]
current_capacity = vehicle_capacity - demand
# Remove the customer from the request bank as it is now assigned
if customer_id in solution.request_bank:
solution.request_bank.remove(customer_id)
# Increment vehicle ID for the next route
vehicle_id += 1
# Add the final route (if there are still customers left)
if current_route:
route = Route(problem, vehicle_id)
route.route = current_route # Assign the customers to the route
routes.append(route) # Add the last route to the routes list
# Check if all requests have been assigned to a route
if 0 in solution.request_bank: # Check if depot is in the request bank (shouldn't be)
solution.request_bank.remove(0) # Remove depot if present
if len(solution.request_bank) > 0:
print(f"Remaining in request bank: {solution.request_bank}")
raise IndexError("There are not enough vehicles to assign all requests")
# Filter the routes to include only those that were used
solution.routes = routes # Use the routes list created earlier
print(
f"Final solution: {solution.routes}, "
f"Number of routes: {len(solution.routes)}, "
f"Number of vehicles used: {solution._number_of_used_vehicles()}"
)
# Rebuild insert matrices to reflect the current state of the solution
solution._rebuild_insert_matrices()
return solution
def _rebuild_insert_matrices(self):
"""
(Re)build the insert matrices.
This method (re)builds _delta_f and _best_insert_position.
Matrices needed by the insert heuristics.
"""
# Creating and initializing matrices
self._delta_f = [[float('inf')]*len(self.routes) for x in range(self.problem.n)]
self._best_insert_position = [[-1]*len(self.routes) for x in range(self.problem.n)]
# For each route
for route_id in self.available_vehicles:
self._update_best_insert_route(route_id)
I have this data:
B-n31-k5
runtime: 831.782910
VEHICLE
NUMBER CAPACITY
100000 100
CUSTOMER
CUST NO. XCOORD. YCOORD. DEMAND
0 17 76 0
1 24 6 25
2 96 29 3
3 14 19 13
4 14 32 17
5 0 34 16
6 16 22 9
7 20 26 22
8 22 28 10
9 17 23 16
10 98 30 8
11 30 8 3
12 23 27 16
13 19 23 16
14 34 7 10
15 31 7 24
16 0 37 16
17 19 23 15
18 0 36 14
19 26 7 5
20 98 32 12
21 5 40 2
22 17 26 18
23 21 26 20
24 28 8 15
25 1 35 8
26 27 28 22
27 99 30 15
28 26 28 10
29 17 29 13
30 20 26 19
Could anyone help me identify why this IndexError is occurring and how I can ensure that all clients are properly included in the solution? Any guidance on managing the routes effectively would be greatly appreciated!
the code of repr :
def __repr__(self):
result = "* Total current cost: %s \n" % self.cost
result += "* (node: [start, departure_load]):\n"
for i in range(len(self.route)):
result += "(%s: [%s, %s]) --> " % (self.route[i],
self.earliest[i],
self.loads[i])
return result
Upvotes: -1
Views: 61
Answers (1)
rajah
Reputation: 21
This code resolve my problem without changing in repr, just changing the get_start_solution
def _get_start_solution(self, problem):
"""
Generate an initial solution for the problem by assigning requests to vehicles
based on vehicle capacity and customer demands.
Parameters
----------
problem : `Problem`
The optimization problem containing vehicles and requests.
Returns
-------
solution : `Solution`
The initial solution object with routes for all vehicles.
"""
# Initialize the solution object
solution = Solution(problem)
num_customers = len(problem.P) # Number of customers (pickup points)
print(f"Number of customers: {num_customers}")
vehicle_capacity = getattr(problem.vehicles[0], 'capacity', 100) # Get vehicle capacity from the first vehicle
print(f"Vehicle capacity: {vehicle_capacity}")
routes = []
vehicle_id = 0 # Start vehicle IDs from 0
# Create a list of customers (excluding depot which is assumed to be customer 0)
customers = list(range(1, num_customers + 1)) # Only customers, not the depot
print(f"Shuffling customers: {customers}")
random.shuffle(customers)
current_route = []
current_capacity = vehicle_capacity
current_loads = [] # To keep track of the loads in the current route
for customer_id in customers:
if customer_id not in problem.P:
print(f"Customer {customer_id} not found in problem.P")
continue # Skip this customer if they do not exist
demand = problem.P[customer_id].load # Assuming demand is stored in 'load'
print(f"Customer {customer_id} demand: {demand}")
# Check if the current vehicle can accommodate the customer's demand
if current_capacity >= demand:
current_route.append(customer_id)
current_capacity -= demand
current_loads.append(demand) # Track the load for this route
# Remove the customer from the request bank as it is now assigned
if customer_id in solution.request_bank:
solution.request_bank.remove(customer_id)
else:
if current_route: # Only append if current_route is not empty
route = Route(problem, vehicle_id)
route.route = current_route
routes.append(route)
# Synchronize earliest, latest, and loads with the route length
route.earliest = [0] * len(current_route) # Assuming default values for earliest
route.latest = [0] * len(current_route) # Assuming default values for latest
route.loads = current_loads # Assign the loads
# Start a new route with a new vehicle
current_route = [customer_id]
current_capacity = vehicle_capacity - demand
current_loads = [demand] # Reset the load for the new route
# Remove the customer from the request bank as it is now assigned
if customer_id in solution.request_bank:
solution.request_bank.remove(customer_id)
# Increment vehicle ID for the next route
vehicle_id += 1
# Add the final route (if there are still customers left)
if current_route:
route = Route(problem, vehicle_id)
route.route = current_route
routes.append(route)
# Synchronize earliest, latest, and loads with the route length
route.earliest = [0] * len(current_route)
route.latest = [0] * len(current_route)
route.loads = current_loads # Assign the final loads
# Check if all requests have been assigned to a route
if 0 in solution.request_bank: # Check if depot is in the request bank (shouldn't be)
solution.request_bank.remove(0)
if len(solution.request_bank) > 0:
print(f"Remaining in request bank: {solution.request_bank}")
raise IndexError("There are not enough vehicles to assign all requests")
solution.routes = routes # Use the routes list created earlier
print(
f"Final solution: {solution.routes}, "
f"Number of routes: {len(solution.routes)}, "
f"Number of vehicles used: {solution._number_of_used_vehicles()}"
)
# Rebuild insert matrices to reflect the current state of the solution
solution._rebuild_insert_matrices()
return solution
Upvotes: 0