Comments (5)
Oh right, so with the current implementation, vehicles may wait around at a location for any amount of time without incurring a cost? That seems like a big problem.
Is my guess right that that your solution would only run after the main optimization is done, when the routes have already been decided? That could lead to a lot of wait time remaining if you're using small time windows.
from node-or-tools.
No - the time vehicles "wait" at a location is the service time (check the docs for durations
.
The difference between the current implementation and minimizing the makespan as ticketed here is minimizing makespan minimizes the time the last vehicle will arrive back at the depot. Basically optimizing getting the full problem done as fast as possible.
Simple example highlighting what's getting minimized:
- Currently: 9 vehicles on the road for 2 hours, 1 vehicle on the road for 8 hours (26 hours -> min)
- Minimizing Makespan: 10 vehicles on the road for 2.6 hours (2.6 -> min) (26 hours)
from node-or-tools.
Aah, got you! 👍
Hmm, what I meant by wait time though is the time a vehicle may have to wait due to time windows. Not the service time, how long it takes to unload a package. This is not something you could program into the cost at the start like you do with travel time, so I am unsure if gets optimized for. And does one hour of waiting have the same cost as one hour of driving then?
from node-or-tools.
We optimize based on costs only. Costs are applied to ways not to locations. What you could do is you could add secondary objectives and then e.g. minimize the arrival time at each location.
from node-or-tools.
@daniel-j-h
My goal is to minimize the total duration on the road instead of the total number of driving hours. My understanding is that I have very little control over the cost function, i.e., I have to define the arc cost via
routing.SetArcCostEvaluatorOfAllVehicles(cost_function)
and the objective function will be either the total cost or the total cost plus the weighted global spans of each dimension on which I called
some_dimension.SetGlobalSpanCostCoefficient(SpanCoefficient)
Hence I can not simply define the objective function to be the max of all routes (instead of the sum).
Following your suggestion above, I create a new dimension, called "time", that uses the same evaluator as the cost but on which I also call AddVariableMinimizedByFinalizer
for each vehicle. To keep it simple I choose constant 1 as the cost. A good solution for 5 drivers and 20 stops should be 4 stops for each driver. The solver still returns a solution in which 1 vehicle does all the work instead of using all available vehicles.
Here is a minimal example, followed by the output of the solution printer:
import ortools.constraint_solver.pywrapcp
import ortools.constraint_solver.routing_enums_pb2
stops = 20
vehicles = 5
depot = 0
routing = ortools.constraint_solver.pywrapcp.RoutingModel(stops, vehicles, depot)
def cost_function(x,y):
return 1
routing.SetArcCostEvaluatorOfAllVehicles(cost_function)
evaluator = cost_function
slack_max = 24 * 60
capacity = 24 * 60
fix_start_cumul_to_zero = True
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)
for vehicle in range(vehicles):
routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.End(vehicle), "time"))
search_params = ortools.constraint_solver.pywrapcp.RoutingModel.DefaultSearchParameters()
assignment = routing.SolveWithParameters(search_params)
Here is the output:
Route for vehicle 0:
0 -> 0
Duration of route 0: 1 minRoute for vehicle 1:
0 -> 0
Duration of route 1: 1 minRoute for vehicle 2:
0 -> 0
Duration of route 2: 1 minRoute for vehicle 3:
0 -> 0
Duration of route 3: 1 minRoute for vehicle 4:
0 -> 19 -> 18 -> 17 -> 16 -> 15 -> 14 -> 13 -> 12 -> 11 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
Duration of route 4: 20 minTotal duration of all routes: 24 min
from node-or-tools.
Related Issues (20)
- npm ERR! .... HOT 1
- What is durations? And how to declare demands? HOT 1
- `ACTION binding_gyp_action_before_build_target_install_deps mason_packages` is called twice on Node 10 HOT 2
- RouteLocks is for establish starting points in order, or to assign points to route to visit optimized?
- Time windows array must include depot?
- Problem when providing pair of pickup and delivery indices
- Problem when considering vehicles with different vehicle speed and capacity in Google OR tools python
- How to minimize number of vehicles and enforce routes to maximize usage
- Inconsistent results when giving additional vehicle even if not required
- Not giving the best (shortest and fastest) route
- Size too large for deployment. Possibilities to reduce size? HOT 1
- [email protected] and [email protected] HOT 6
- How to package google official ortools into static link library
- can't use the package in mac
- how to declare demands ? HOT 1
- Ouput examples on a local webserver
- Windows build
- Usage/Installation on node-alpine
- BUG: amazonaws links not accessible
- Pre build binaries missing for v1.1.0 (OSX + node 14.20.1)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from node-or-tools.