minimize total distance and number of vehicles, CVRPTW, also limit the number of clients in each route

[Wei BI]

Hello there! 

I am working on construction waste collection vehicle routing problem with python. The scenario is that:

(1) There are 2775 orders with different demands generated by 290 clients. Each order is linked with a client index and a time window. 

(2) There are 680 trucks available to serve these orders. Trucks also have different maximum load capacity.

(3) Assume that each truck sets off from a depot and serves orders within the time window constraints. I only need to make sure that the demand of each order a truck served ≤ truck's load capacity instead of accumulative demands of all orders served by each truck ≤ truck's load capacity. After a day's work, truck need to go back to the depot.

The key constrains I want to set is:

(1) the demand of each order it served ≤ truck's load capacity;

(2) time window constraint of each order

(3) limit the number of clients ≤ 4 (2775 orders from 290 clients, so one client can have multiple orders, I want to limit the the number of clients each truck serves)

The objective is:

(1) minimize the total distance of all routes

(2) on top of that, minimize the number of trucks used (I learned from some tutorials that this can be realized by adding penalty)

I have distance_matrix and duration_matrix from order to order, time_window of each order, load capacity of trucks, and demands of each order. 

I'm trying to revise the CVRPTW example from or-tools GitHub (see https://github.com/google/or-tools/blob/stable/examples/python/cvrptw_plot.py). But I got several confusions:

(1) What is the objective of this CVRPTW example? It seems to be the total cost. What should I do if I want to set _the total distance_ as my objective?

(2) How can I get and print the route distance of each vehicle?

(3) What is the role of the "box_size" in your coding?

(4) How can I limit the demand of each order a truck served ≤ truck's load capacity?

(5)  How can I limit the number of clients in each route?

Please see the code in the attachment. It's not working. Error in the terminal is:

Sorry if this is too long. I am a beginner of Python. I really hope to get help from you experts with regards to the aforementioned questions and the coding.

Thank you!

[Mizux Seiha]

Hi,

You should start from a simpler sample like this cvrptw.py : https://gist.github.com/Mizux/4870e4af09b31dd45b7ac632d1830a73 
 
1) the demand of each order it served ≤ truck's load capacity:
You can use routing.VehicleVar(index).SetValues([list_of_vehicle_allowed]) 

note: if node is droppable you can add the value -1 too

ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L1224-L1226

2) time window constraint of each order
see sample...

(3) limit the number of clients ≤ 4 (2775 orders from 290 clients, so one client can have multiple orders, I want to limit the the number of clients each truck serves)

I would create one dimension per client with a transit being +1 for a node which belongs to this client
Then i'll add a constraint for each vehicle end node the sum of non zero client's dimension must be less than 4.

[Wei BI]

Hi Mizux,

Sincerely thanks for your response! 

After looking through the simple example you recommended, I still got several questions:

1. What is the unit of time in this CVRPTW example? Is it in seconds or minutes?
2. I don't need data['pickups_deliveries']. When I delete the "Define Transportation Requests" part in "main" function, will it affect other parts or the results?
3. For response 1) in your email, do you mean replace "routing.AddDimensionWithVehicleCapacity" part in "Add Capacity constraint" in your simple example with "routing.VehicleVar(index).SetValues([list_of_vehicle_allowed]) ", like this:
4. For response 3) in your email, could you help me code this constraint?
   

My appreciation is beyond words. Looking forward to your reply.

Best regards,

Wei

[Mizux Seiha]

1. Sover is dimension agnostic so you can use anything you want, two rules:
- must be integer (std::int64_t)
- try to use the lowest resolution possible e.g. 1 unit == 13min instead of 1unit==1ms if it makes sense for your problem

2. no its ok to supress if you don't have any Pickup and Delivery locations pair

3.If I recall correctly you only want to filter vehicle so you don't need the whole left part, I would see something like this
```python
vehicle_capacity = [ 7, 11, 13, 31, 97, ....]
location_minimum_capacity = [0, 1, 1, 2, 3, 5, 7, 13, 21, 34]

for idx, capacity in enumerate(location_minimum_capacity):
     if idx in Starts or idx in Ends:

        continue

    vehicles = []
    for vehicle_id in range(manager.GetNumberOfVehicles()):

        if  capacity < vehicle_capacity[vehicle_id]:

            vehicles.append(vehicle_id)

    routing.VehicleVar(manager.NodeToIndex(idx)).SetValues(vehicles)
```

4) How can I limit the demand of each order a truck served ≤ truck's load capacity?

seems to be exactly the purpose of the left image...

[Wei BI]

Thank you for your help!

I tried your simple example of CVRPTW, but no solution found. I attached my coding. I don't know where is wrong. Please help me check it.

Btw, further two more questions:

1. Must the demand and capacity in data['demands'] and data['vehicle_capacities'] also be integer?
2. Could you pls help me with the coding of constraint - "limit the number of clients ≤ 4 (2775 orders from 290 clients, so one client can have multiple orders, I want to limit the the number of clients each truck serves)"? I have data['demands'] and data['clients']. Each demand in  data['demands'] corresponds to a client_id in data['clients'] with the same index.
   

Regards,

Wei