search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
10.84k stars 2.09k forks source link

I need a vehicle to make multiple trips #976

Closed pmvbajpai closed 4 years ago

pmvbajpai commented 5 years ago

I am using OR Tools using Python and would like to use multiple trips of a vehicle as the cost of using that vehicle is less compare to other vehicle. Could you please suggest me about the same?

Problem Statement:

  1. TS09UA5627 - (Capacity - 20) - (Cost - 5)
  2. TS09UB7297 - (Capacity - 50) - (Cost - 100)
  3. TS09UA8646 - (Capacity - 75) - (Cost - 150)
  4. TS08UV9283 - (Capacity - 80) - (Cost - 160)
  5. TS09UA2435 - (Capacity - 85) - (Cost - 170)

I would like to use vehicle 1 many times as cost is saved.

Mizux commented 5 years ago

You need two things:

pmvbajpai commented 5 years ago

Thanks a lot for the information. I have duplicated the depots as you mentioned. Added last 2 in the attached sheet.

SetFixedCostOfVehicle was already added in my python script as I am using cvrptw_plot.py to solve my constraints.

This still is not repeating the vehicle and using the individual vehicles. Could you please let me know what am I doing wrong. (I have added comments in the CSV file attached below)

Thanks in advance !!

routeParameters.xlsx

Mizux commented 5 years ago

Are you sure the TW at each locations allow one vehicle to travel back to depot then perform the next "trip". Otherwise the solver has to use other vehicle to be on time at each location...

pmvbajpai commented 5 years ago

Yes, I have tried with a large time window of 16 hours for nearby locations but its not working. Also, I can give only time in hours and minutes, I cannot assign dates in time windows - is there a way out please?

Mizux commented 5 years ago

Please provide a code source, otherwise take a second look at cvrp_reload.py

pmvbajpai commented 5 years ago

Please find the code in the zip format.

final.py is the file which takes parameters from routeParameters.csv

Thank you for all the help.

final code.zip

pmvbajpai commented 5 years ago

Did you get some time to check the code please?

DavidLSmyth commented 5 years ago

I'm also interested in figuring this out, I am trying to plan routes for a heterogeneous (they work with different fuel capacities, operational speeds, service times) fleet of vehicles to visit a set of points, with the ability to return the the depot to recharge and then set out again, with the objective to minimize total time taken to visit all points. A single, well-documented example of how this could be done would help close some related issues (#862, #878). I am close to finding a solution but I'm not sure it's the 'right' way to model it using the tools provided in this repo.

Thanks for the fantastic work done to create ortools!

CognitiveClouds-Prasad commented 5 years ago

Can anybody let me know as to when this would be added?

lperron commented 4 years ago

See https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py

lperron commented 4 years ago

You should use the latest version of or-tools (7.3).

Le mer. 7 août 2019 à 01:14, kongxiangmao notifications@github.com a écrit :

https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py when run this code, it has the error information like bellow: Traceback (most recent call last): File "/Users/sf/Desktop/code/python/VRP/code/cvrp_reload.py", line 326, in main() File "/Users/sf/Desktop/code/python/VRP/code/cvrp_reload.py", line 292, in main manager = pywrapcp.RoutingIndexManager(data['num_locations'], AttributeError: module 'ortools.constraint_solver.pywrapcp' has no attribute 'RoutingIndexManager'

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/976?email_source=notifications&email_token=ACUPL3KWXNPUST567BUYGBTQDJ77JA5CNFSM4GKYIMEKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD3XTBBY#issuecomment-518992007, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3NUE5AZKT3WYARYUH3QDJ77JANCNFSM4GKYIMEA .

jagratigogia42 commented 3 years ago

You need two things:

Hi @Mizux , Actually trying to find a workaround for the exact same goal, to be able to use the same vehicle to do multiple trips, i.e. any number of trips that is feasible in the given time window.

Your solution references a code link, but it's broken. Could you update the link or point me to a solution for the problem mentioned here?

Thanks.

Mizux commented 3 years ago

@jagratigogia42 moved to ortools/constraint_solver/samples: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py EDIT: Just fixed the path in the previous post...

ViveK-PothinA commented 3 years ago

Hello @Mizux

I'm also trying to solve for the same vehicle to do multiple trips feasible in the time window.

I have tried out the cvrp_reload sample: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py

I have modified it, so that I can handle lat lng in locations and I'm using radial distance instead of manhattan distance. But I'm getting 0km output for all vehicles, basically the solver is saying there is a solution, but all are 0.

Objective: 300000
dropped orders: [6, 7, 8]
dropped reload stations: [6, 7, 8, 1, 2, 3, 4, 5]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 1:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 2:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 3:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 4:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 5:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 6:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 7:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 8:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 9:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Total Distance of all routes: 0m
Total Load of all routes: 0
Total Time of all routes: 0min

This is gist link to the modified code: https://gist.github.com/ViveK-PothinA/a85445d79e6ee302129f927b29c55c33

Please help me identify where I'm going wrong. Thanks in advance.

abvhove commented 3 years ago

@jagratigogia42 moved to ortools/constraint_solver/samples: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py EDIT: Just fixed the path in the previous post...

Thanks for the link. But can you help in a case where the capacity of the vehicles are different ? I have 31 vehicles with 4 different capacities. I'm looking for a solution where the vehicles return to the depot when they're empty but can't get the solution ...

GeorgeLeucuta commented 2 years ago

Hello @Mizux

I'm also trying to solve for the same vehicle to do multiple trips feasible in the time window.

I have tried out the cvrp_reload sample: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py

I have modified it, so that I can handle lat lng in locations and I'm using radial distance instead of manhattan distance. But I'm getting 0km output for all vehicles, basically the solver is saying there is a solution, but all are 0.

Objective: 300000
dropped orders: [6, 7, 8]
dropped reload stations: [6, 7, 8, 1, 2, 3, 4, 5]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 1:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 2:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 3:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 4:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 5:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 6:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 7:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 8:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 9:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Total Distance of all routes: 0m
Total Load of all routes: 0
Total Time of all routes: 0min

This is gist link to the modified code: https://gist.github.com/ViveK-PothinA/a85445d79e6ee302129f927b29c55c33

Please help me identify where I'm going wrong. Thanks in advance.

Hello, Did you manage to find a solution for this issue?

Mizux commented 2 years ago

@GeorgeLeucuta

  1. Your distance callback must return an int

    def distance_evaluator(manager, from_index, to_index):
    """Returns the manhattan distance between the two nodes"""
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    dst = int(_distances[from_node][to_node]) # see the cast here
    #print(f'dst: {dst}') # for debug purpose
    return dst

  2. also all your distance seems to be around 10k-25k so to incentive the solver to avoid to drop the node you need to increase the penalty

    # Allow to drop regular node with a cost.
for node in range(6, len(data['demands'])):
    node_index = manager.NodeToIndex(node)
    capacity_dimension.SlackVar(node_index).SetValue(0)
    routing.AddDisjunction([node_index], 10_000_000)

Then possible output:

./cvrp_reload_1.py
Objective: 9258964
dropped orders: []
dropped reload stations: [1, 2, 3, 4, 5]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 1:
 0 Load(0) Time(0,0) -> 8 Load(0) Time(109,120) -> 0 Load(3) Time(233,1500)
Distance of the route: 90956m
Load of the route: 3
Time of the route: 233min

Route for vehicle 2:
 0 Load(0) Time(0,0) -> 7 Load(0) Time(61,120) -> 0 Load(3) Time(137,1500)
Distance of the route: 51538m
Load of the route: 3
Time of the route: 137min

Route for vehicle 3:
 0 Load(0) Time(0,0) -> 6 Load(0) Time(60,120) -> 0 Load(3) Time(100,1500)
Distance of the route: 20870m
Load of the route: 3
Time of the route: 100min

Total Distance of all routes: 163364m
Total Load of all routes: 9
Total Time of all routes: 470min

note: I set vehicle to 4 instead of 10 (BTW you only have 3 node other are reload nodes...)

GeorgeLeucuta commented 2 years ago

@GeorgeLeucuta

  1. Your distance callback must return an int
    def distance_evaluator(manager, from_index, to_index):
        """Returns the manhattan distance between the two nodes"""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        dst = int(_distances[from_node][to_node]) # see the cast here
        #print(f'dst: {dst}') # for debug purpose
        return dst
  1. also all your distance seems to be around 10k-25k so to incentive the solver to avoid to drop the node you need to increase the penalty
    # Allow to drop regular node with a cost.
    for node in range(6, len(data['demands'])):
        node_index = manager.NodeToIndex(node)
        capacity_dimension.SlackVar(node_index).SetValue(0)
        routing.AddDisjunction([node_index], 10_000_000)

Then possible output:

./cvrp_reload_1.py
Objective: 9258964
dropped orders: []
dropped reload stations: [1, 2, 3, 4, 5]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 0 Load(0) Time(0,1500)
Distance of the route: 0m
Load of the route: 0
Time of the route: 0min

Route for vehicle 1:
 0 Load(0) Time(0,0) -> 8 Load(0) Time(109,120) -> 0 Load(3) Time(233,1500)
Distance of the route: 90956m
Load of the route: 3
Time of the route: 233min

Route for vehicle 2:
 0 Load(0) Time(0,0) -> 7 Load(0) Time(61,120) -> 0 Load(3) Time(137,1500)
Distance of the route: 51538m
Load of the route: 3
Time of the route: 137min

Route for vehicle 3:
 0 Load(0) Time(0,0) -> 6 Load(0) Time(60,120) -> 0 Load(3) Time(100,1500)
Distance of the route: 20870m
Load of the route: 3
Time of the route: 100min

Total Distance of all routes: 163364m
Total Load of all routes: 9
Total Time of all routes: 470min

note: I set vehicle to 4 instead of 10 (BTW you only have 3 node other are reload nodes...)

Hello @Mizux,

First of all thank you very much for your support!

Your scenario seems to only work when the vehicle capacity is equal between all the vehicles. In my case the cars have different capacities. It is possible to adapt it to take this factor into consideration? Or is it possible to modify the demand_callback function so that it sets the vehicle load to 0 for specific nodes(depot)? If so, can you please provide an example?

Also, if I have 10 vehicles in my list and I want every vehicle to be able to return to the depot should I add 10 more depots? I'm asking because I would like for the algorithm to allow an unlimited number of returns to the depot for all vehicles as long as the trip times fit the time window of each vehicle. Is there a solution to this?

Thanks a lot!

Mizux commented 2 years ago

yes you'll need to duplicate depot several times i.e. one per "potential reload"

GeorgeLeucuta commented 2 years ago

yes you'll need to duplicate depot several times i.e. one per "potential reload"

@Mizux

Thank you!

Can you please give me an idea on how to approach the first issue?

"Your scenario seems to only work when the vehicle capacity is equal between all the vehicles. In my case the cars have different capacities. It is possible to adapt it to take this factor into consideration? Or is it possible to modify the demand_callback function so that it sets the vehicle load to 0 for specific nodes(depot)? If so, can you please provide an example?"

Best regards!