Skip to main content
4 votes

Gurobi spend more time in presolve in small model without removing anything

It is a general misconception that presolve reduces the size of the problem. While this is a typical side effect, the actual goal of the presolving step is to find an equivalent model that is more ...
mattmilten's user avatar
  • 1,653
4 votes
Accepted

Unable to find good solution for CVRP with Time Window

If you are fine with using an heuristic solver, that does not provide you gaps or bounds, you can use PyVRP. It employs the current state-of-the-art heuristic for the VRPTW (Hybrid Genetic Search). ...
PeterD's user avatar
  • 1,706
3 votes
Accepted

In which circumstances is it sufficient to branch on the flow on edges to ensure integrality in VRPs?

It really depends on the problem and on the formulation that is used. For example, in the following paper the authors compare different formulations for the CVRP, some of which are defined on arcs and ...
Kevin Dalmeijer's user avatar
3 votes
Accepted

Flow conservation constraints for an Open Vehicle Routing Problem

I'm not familiar with the published literature, but a simple fix is to create an artificial terminating node to which all vehicles must go, along with zero-length arcs from every node to the ...
prubin's user avatar
  • 39.6k
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 -...
Alberto Santini's user avatar
3 votes
Accepted

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 ...
Claudio Contardo's user avatar
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 ...
prubin's user avatar
  • 39.6k
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 ...
Christopher Cho's user avatar
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
Oguz Toragay's user avatar
  • 8,667
2 votes
Accepted

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 ...
Kuifje's user avatar
  • 13.5k
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 ...
RobPratt's user avatar
  • 32.8k
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, ...
prubin's user avatar
  • 39.6k
1 vote

Unable to find good solution for CVRP with Time Window

I think it is important to note that even thought the gap is large (15%) the solution may still be very good, actually. My experience is that the linear programming bound obtained for most models of ...
Sune's user avatar
  • 6,647
1 vote

Implementing soft time window constraints with time_matrix dependent on vehicle types

I was able to fix this. I checked on following points: time callback function must return an integer and not float. You can not add time window constraints on depots. ...
mufassir's user avatar
  • 211
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 ...
prubin's user avatar
  • 39.6k
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 ...
fontanf's user avatar
  • 2,623
1 vote
Accepted

Optimizing a Route Selection Problem with Multiple Constraints and Objectives

Thanks to @Nelewout and his work on library PyVRP it super easy to setup and solve this Vehicle Routing Problem with prize collection (scores) and even with time windows, using heuristics. ...
Rastislav's user avatar
  • 131
1 vote

A hard VRP with Time Windows + Multi Routes

Your problem is a form of multi-vehicle routing problem with time windows (frequently abbreviated m-VRPTW, although I believe I've also seen MVRPTW). Searching for that will turn up a variety of ...
prubin's user avatar
  • 39.6k
1 vote
Accepted

Vehicle Routing Problem with Two fleets

Also since depot $0$ is not part of $C$ so for arcs$(0,4),(4,0)$ constraint 8 isn't applicable. Together with bounds on counters $y$ or $z$ the solver finds $x_1$ more feasible so long it meets ...
Sutanu Majumdar's user avatar
1 vote

Capacited Vehicle Routing Problem with flow formulations

Assuming your customers are $N =\{1,2,...5 \}$ while nodes $N+\{0\}$, subtour elimination constraint involves $(3,1)$ and $(4,5)$ $y_1 + 16 \le y_3 \le 19 = (35-16)$ and $y_5 + 11 \le y_4 \le 12$ $y_4 ...
Sutanu Majumdar's user avatar
1 vote
Accepted

Capacited Vehicle Routing Problem with flow formulations

Assuming that $y_i$ is the load in the vehicle when exiting customer $i$ (after dropping of $d_i$ units of goods there), then your first constraint has an incorrect middle term. It should be $$y_j \le ...
prubin's user avatar
  • 39.6k
1 vote
Accepted

Gurobi spend more time in presolve in small model without removing anything

In the log you show, the Presolve parameter was changed to 2. That value corresponds to an aggressive setting. It can therefore be expected that presolve takes longer than when left at the default ...
Xavier Nodet's user avatar
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 ...
prubin's user avatar
  • 39.6k
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'. ...
Abilash's user avatar
  • 63

Only top scored, non community-wiki answers of a minimum length are eligible