6
votes
Accepted
How to partition a giant tour into feasible routes?
Here’s a MILP formulation to partition an Eulerian graph into $K$ Eulerian subgraphs, with an objective of minimizing the maximum cost. Let binary decision variable $x_{ijk}$ indicate whether edge $(...
- 30.5k
4
votes
Accepted
Routing problem - How can I make use of the Clarke and Wright algorithm for a CVRP, when using the ortools library?
You need to replace PATH_CHEAPEST_ARC by SAVINGS.
See https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/...
- 2,587
3
votes
Late and Early Costs per minute for a delivery problem
The constraints you need to set the value of variables $A_i$ correctly are a generalisation of the famous Miller-Tucker-Zemlin (MTZ) constraints.
For example, you can use $A_j \geq A_i + t_{ij} - M(1 -...
- 2,073
3
votes
Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?
You usually use Benders decomposition when a large number of variables and linking constraints can somehow be removed without significantly affecting the structure of your problem.
In your case, you ...
- 1,549
3
votes
How to construct LIFO constraints in Pickup and Delivery Problem
Basically it says after the last pickup vehicle $k$ doesn't visit any other node unless the node is a delivery point $\in D$ for the last picked up request.
Hierarchical Objective - minimize travel ...
- 3,343
2
votes
How to partition a giant tour into feasible routes?
Here is an alternative to RobPratt's precise solution.
First, compute all simple cycles of the graph $G=(V,A)$ (the graph can be directed in an arbitrary direction). Then, compute $2$-cycles and $3$-...
- 12.9k
2
votes
List of Implementations for common OR problems
I just want to mention the solvers that have been produced in recent years in the remit of the PACE (Parameterized Algorithms and Computational Experiments) challenge, see https://pacechallenge.org/.
...
- 25
2
votes
how to satisfy time constraints with meeting points?
You can refer to Google OR example for more information but it seems you'd need a time matrix $T$ between locations $(i,j)$
Then for each driver it will be set of constraints
$ a_d+\sum_{i,j}x_{i,j}^...
- 3,343
2
votes
Heuristics for selecting the right fleet combinations for a VRP
You could for example adapt the well known Clarke & Wright algorithm and only generate routes that meet all of the required constraints.
This is precisely what is done in the VRPy library. You can ...
- 12.9k
2
votes
Accepted
Kim et al.'s (2006) waste collection VRP-IF
Here I found the correct link: http://logistics.postech.ac.kr/benchmark.html
- 8,622
2
votes
Solving a VRP variant with time constraints
What is the incentive for using the vehicles? Nothing in your model requires that any demand be satisfied, so the cheapest solution clearly is to do nothing. If you are required to meet cell demands, ...
- 37.8k
2
votes
Scheduling & Routing Problem
One possibility might be to start by constructing feasible one-day schedules for techs (service just A, service A and B in some order, service A, B and C in that order, ...). The MILP model would then ...
- 37.8k
2
votes
Accepted
Google Cloud Fleet Routing... what types of VRPs does it cover?
https://cloud.google.com/blog/products/ai-machine-learning/google-cloud-optimization-ai-cloud-fleet-routing-api
and
https://cloud.google.com/optimization/docs/reference/rpc
may help. Generally, CFR ...
2
votes
Travelling salesman problem
The MTZ constraints are big-M constraints that enforce the logical implication
$$x_{ij}=1\implies u_j\ge u_i+d_j.$$
That is, if you traverse arc $(i,j)$, the cumulative demand at $j$ is at least the ...
- 30.5k
1
vote
Optimization algorithm for space debris
ACO, genetic algorithms and other metaheuristics can be adapted to constrained problems by adding to the objective function penalties for constraint violations and then treating the problem as ...
- 37.8k
1
vote
Is there existing code for the set partitioning formulation of routing problems?
Python is not an efficient language, and solving the resource constrained shortest path is the bottleneck of the branch-and-cut-and-price algorithms for routing problems. Therefore, you won't find a ...
- 2,495
1
vote
Late and Early Costs per minute for a delivery problem
The problem you are describing is a version of what is known as a Vehicle Routing Problem with Time Windows (VRPTW). If you enter VRPTW in the search box for this site, you'll find a gaggle of ...
- 37.8k
1
vote
Accepted
does mTSP/CVRP always minimize number of vehicles used?
I found one such instance(from the "P" datasets) and i distilled it to just the customers who will result in this 'phenomenon'.
...
- 63
1
vote
What are the most popular papers on Uber-type spatial matching?
I advise you to look at the following paper. The authors look at pure online strategies where a decision is made instantly but also look at re-optimization strategies.
Bertsimas, D., Jaillet, P., &...
- 1,461
1
vote
how to satisfy time constraints with meeting points?
I'm going to make the following assumptions.
No driver and no rider ever visits the same node twice. (It is possible to work around this assumption by adding arcs to the graph, but that makes the ...
- 37.8k
1
vote
Accepted
Alternative Approaches to Assignment Problem
If you are open to heuristic (approximate) solutions, one possibility is to generate a set of routes and then rewrite the problem to assign trucks and customers/orders to routes. In problems of this ...
- 37.8k
1
vote
Alternative Approaches to Assignment Problem
It seems that you are trying to solve a pickup and delivery problem. MIP solvers are often not the best tool for that, and getting good results with them requires special models and tricks.
There are ...
- 1,842
1
vote
Accepted
How to mathematically model this vehicle routing with pickup and deliveries problem?
The below is what I put in in another answer. It has additional LiFO constreaint- last load pickup, first to be dropped.
Basically it says after the last pickup vehicle $k$ doesn't visit any other ...
- 3,343
1
vote
Accepted
TypeError: unsupported operand type(s) for *: 'IntVar' and 'float' in ortools
This is solved as follows:
2 * capacity_dimension.CumulVar(idx) * routing.ActiveVar(idx) >= capacity_dimension.CumulVar(routing.End(v))
- 181
Only top scored, non community-wiki answers of a minimum length are eligible