Skip to main content

Questions tagged [vehicle-routing]

For questions related to optimization problems for routing vehicles through a set of nodes, especially the vehicle routing problem (VRP) and its variants.

Filter by
Sorted by
Tagged with
1 vote
1 answer
44 views

Real problem in capacity planning in transport network - operational level

I need to find a real problem for my thesis and I'm reviewing the literature. The topic is operational capacity planning in transport networks. I understand I need to find a real-world problem at the ...
Trang Ly's user avatar
2 votes
5 answers
180 views

Unable to find good solution for CVRP with Time Window

I am trying to solve Capacitated VRP with Time Window for 50 demand points. I was trying to optimize this in Gurobi Solver but it doesn't give good answer like optimality gap is 30% or more. Any idea ...
Maths_hawk's user avatar
2 votes
0 answers
46 views

Does there exist a constant factor approximate solution for capacitated vehicle routing problem?

I know that there is a 1.5 approximate solution for metric traveling salesman problem (TSP), e.g., Christofedes algorithm guarantees this. Is there an algorithm that guarantees a constant factor ...
Krypt's user avatar
  • 97
0 votes
0 answers
61 views

Solving a multi depot multi vehicle capacitated routing problem using global constraints

I have built the model, but at this point, I am not sure how do I ensure that each fighter starts from the assigned depot and comes back to that depot. here is my code. The ...
Shahrukh Mohd's user avatar
0 votes
1 answer
122 views

Generating a good initial solution for a problem

I am solving an extended version of VRP, namely prize collecting VRP with incomplete service. There are its characteristics: It's a VRP where you collect prizes for each fullfilled demand you don't ...
applethal's user avatar
2 votes
1 answer
127 views

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

I know that it is common to branch on the flow on arcs to ensure intergrality when solving VRPs, but in which circumstances is valid to branch on the flow on edges instead of arcs? References to ...
gmn's user avatar
  • 676
2 votes
1 answer
93 views

Flow conservation constraints for an Open Vehicle Routing Problem

I'm currently reviewing literature on the Open Vehicle Routing Problem (Open VRP), which characterizes scenarios where trucks do not return to the depot after serving the last customer. In this ...
BobHU's user avatar
  • 165
2 votes
1 answer
117 views

Optimizing a Route Selection Problem with Multiple Constraints and Objectives

I'm developing a solution to optimize a vehicle routing problem where each stop has an associated score (priority), specific geo coordinates, and a required stop duration. The goal is to maximize the ...
Rastislav's user avatar
  • 131
1 vote
1 answer
87 views

A hard VRP with Time Windows + Multi Routes

I'm working on a complex VRP problem. I'm working on the generic case, but for you to understand better I've created a small instance.... Assume that there are 3 demand (D1-D2-D3) and 3 supply nodes (...
Evren Guney's user avatar
1 vote
0 answers
84 views

Vehicle Routing Problem OR-tools - Distance between solutions / vehicles

I have an alternative problem which I reckon can be solved using OR-tools. For this problem, apart from the distance between nodes within a solution, I also need the distance between the n-th node of ...
Jigeli's user avatar
  • 11
0 votes
1 answer
128 views

Vehicle Routing Problem with Two fleets

Based on the suggestion in the comment below. I edited my model by removing $w$. Here is the context: I'm dealing with the CVRP with two heterogeneous fleets with the following capacities $q_1$ and $...
MAYA's user avatar
  • 129
1 vote
2 answers
124 views

Capacited Vehicle Routing Problem with flow formulations

I'm trying to solve the CVRP based on flow-formulation. In such a model, we have a decision variable with two-index, $x_{ij}$, where I'm using the MTZ formula to eliminate sub-tours. We have then a ...
MAYA's user avatar
  • 129
0 votes
2 answers
198 views

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

I have a small model to optimize in Gurobi. The problem is that it takes a lot of time in presolve without removing any rows or variables. I tried to disable PreSolve parameter and reduce the number ...
MAYA's user avatar
  • 129
1 vote
1 answer
86 views

Implementing soft time window constraints with time_matrix dependent on vehicle types

I am solving a CVRPTWPD using Google ORTools. Here, objective is to minimize the travelled distance and not time. I have start locations for each vehicle but arbitrary end locations are possible. I ...
mufassir's user avatar
  • 211
4 votes
1 answer
176 views

What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?

Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints. Sadly, at the moment it is not performing fast ...
Arctic_Skill's user avatar
0 votes
1 answer
101 views

Travelling salesman problem

This is a CVRP problem and I have difficulty understanding the constraints in the red box. For the sub-eliminator constraint (MTZ), my question is how can we make it on our own? I am sure there is ...
uni_lad's user avatar
  • 39
0 votes
0 answers
63 views

Travelling Salesman problem and Vehicle routing problems

Can someone explain to me why are we doing the $x_{ij}=1$ and and the constraint $U_j \geq u_i+1-n(1-x_{ij})$ Also do you have any books or sources in mind from where I could learn in more detail from ...
uni_lad's user avatar
  • 39
1 vote
1 answer
99 views

Optimization algorithm for space debris

I'm currently working on a research project to optimize the recovery of space debris. We have to recover 50 pieces of space debris with the minimum number of missions possible. The missions are sent ...
HunKhle's user avatar
  • 11
-2 votes
2 answers
98 views

Is there existing code for the set partitioning formulation of routing problems?

The set partitioning formulation of routing problems is pretty well-accepted as perhaps the best exact method to solve routing problems. However, these methods are difficult to implement as many ...
IsalanOnkar's user avatar
1 vote
1 answer
124 views

Scheduling & Routing Problem

Looking for some advice on how to approach this combo scheduling + routing problem. I am a supply chain OR consultant, and was recently approached by a potential client. Without giving too much away, ...
Ralph Asher's user avatar
1 vote
2 answers
163 views

Google Cloud Fleet Routing... what types of VRPs does it cover?

I'm familiar with solving VRPs in Google's ortools. Has anybody used Google's new Cloud Fleet Routing capability (separate from ...
Ralph Asher's user avatar
0 votes
0 answers
147 views

In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?

In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an elementary path, meaning that no vertices are repeated. However, when an elementary path is ...
IsalanOnkar's user avatar
0 votes
1 answer
109 views

Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?

I am in the process of trying to solve a VRP with synchronization constraints with Benders Decomposition. I am programming in C++ and my approach seems to be really slow for the following reason: My ...
Arctic_Skill's user avatar
1 vote
2 answers
102 views

In a routing and scheduling problem with break consideration, How can I determine whether a node is met before a break or after it?

I'm working on a routing and scheduling problem in the home care services context. I consider a break as a dummy patient, so routing and scheduling are also implemented for the break node (with some ...
Hani Jamshidian's user avatar
1 vote
2 answers
185 views

Help with Mathematical Formulation for VRP with Specific Constraints

I am currently working on a Vehicle Routing Problem (VRP) with a set of specific constraints. I have a total of 19 nodes, each representing a customer location, and a depot. There are also 7 pickers ...
Ilyass's user avatar
  • 19
0 votes
0 answers
36 views

When is time window reduction applicable?

Desrochers, Desrosiers and Solomon (1992) presents a method for reducing the size of the time windows for the VRPTW. Given other versions of the VRPTW, what are the requirements on the problem for it ...
gmn's user avatar
  • 676
2 votes
1 answer
84 views

Kim et al.'s (2006) waste collection VRP-IF

I cannot find a link for the instances of Kim et al.'s (2006) waste collection VRP-IF. https://www.sciencedirect.com/science/article/pii/S0305054805001322. The link mentioned in the paper and the ...
OR Junior's user avatar
  • 543
4 votes
2 answers
71 views

Late and Early Costs per minute for a delivery problem

I'm currently struggling with a MIP. Have to model a truck delivering packages for customers in the set $C = \{1,2,3,4,5\}$. The travel time from location $i$ to $j$ I've defined as $t_{ij}$. The ...
Todd's user avatar
  • 41
3 votes
0 answers
44 views

Adding synchronisation constraint in Prize-collecting VRPTW

I am solving a Prize Collecting VRPTW. In my problem, each node represents a visit that needs to be made within a certain time window, and the "prize" for each node is the time spent at the ...
orman's user avatar
  • 33
0 votes
1 answer
59 views

Heuristics for selecting the right fleet combinations for a VRP

In most VRPs, we start from a set of fleets (homogeneous or heterogeneous) and a set of points to be served. Then there are other constraints that need to be taken care of. I am looking for a ...
Shibaprasad's user avatar
-1 votes
1 answer
68 views

does mTSP/CVRP always minimize number of vehicles used?

Context: I was working on some VRP solvers and realized that tractability deproved when I added Fixed Cost for each vehicle (in an attempt to reduce number of vehicles used). Questions: 1- Due to the ...
Abilash's user avatar
  • 63
0 votes
2 answers
68 views

Solving a VRP variant with time constraints

I am trying to solve a VRP variant where I have a list of vehicles. If a vehicle is used/rented, a cost will be incurred. If not, there will be no cost. And even if a vehicle is rented, it can only be ...
Shibaprasad's user avatar
1 vote
1 answer
176 views

Routing problem - How can I make use of the Clarke and Wright algorithm for a CVRP, when using the ortools library?

TL;DR: How can I specify to ortools to use only the Clarke and Wright algorithm. Hello, I'm trying to solve a CVRP. When exploring the my options, I stumble by the ortools library, it gets the job ...
user.mokho's user avatar
1 vote
1 answer
65 views

What are the most popular papers on Uber-type spatial matching?

This is probably one of those "just google it" kinds of questions, but is there a commonly-accepted "definitive" model in the literature for capturing the kind of matching problem ...
Rebecca Donnelly's user avatar
0 votes
0 answers
711 views

VRP - Clarke and Wright implementation in python unable to find routes

Here's my attempt to implement the clarke and wright algorithm with the following constraints: maximum truck capacity, maximum distance traveled by a truck. The algorithm takes a distance matrix to ...
user.mokho's user avatar
1 vote
2 answers
175 views

how to satisfy time constraints with meeting points?

I have a specific pickup and delivery problem to work on and am thinking how to incorporate time windows effectively. The problem has some driver with some time window [$a_d, b_d$] which is the start ...
Hemfri's user avatar
  • 33
1 vote
0 answers
71 views

How to consider time cost in VRP with BPC method

When we use branch, price and cut method to solve VRPTW problems, the objectives is always: minimize the total distance, or minimize the sum of distance-related variable cost and truck-related fixed ...
Shuyang Zhang's user avatar
1 vote
0 answers
31 views

Understanding queueing theory used to model the vehicle routing problem

I am trying to understand some journal articles on the vehicle routing problem, specifically Vehicle routing with dynamic travel times: A queueing approach and An M/M/c queue model for vehicle routing ...
Andrew's user avatar
  • 163
1 vote
2 answers
111 views

Alternative Approaches to Assignment Problem

I have a real world use case where I aim to optimize the assignment of trucks to orders of different sizes over a time window by minimizing some cost function (e.g. total distance traveled). The below ...
Jordan C's user avatar
0 votes
0 answers
76 views

a solver for large instances of ACVRP

I want to solve large instances of asymmetrical capacitated vehicle problem with thousands of nodes. So far I tried lkh-3 solver but so far I cannot reach noticably better results compared to naive ...
gregy4's user avatar
  • 189
3 votes
0 answers
74 views

Triangular inequality in Routing or Pickup/Drop off problem

I have a multi-pickup dropoff problem where orders from pickup locations need to be dropped off at delivery locations. I converted the problem into a three-index pickup drop-off problem with time ...
mars's user avatar
  • 629
1 vote
1 answer
74 views

How to mathematically model this vehicle routing with pickup and deliveries problem?

I have this problem right here There are N passengers whose are at places 1,2,...,N respectively. The i-th passenger, who is currently at place i, wants to go to place i+N. There are K buses are ...
duyanhhz's user avatar
2 votes
0 answers
50 views

A 'capacitated' VRP model where the capacity constraint is the time

I am trying to model a capacitated VRP model where the capacity is defined by the time the vehicle is available. What I have: List of vehicles available and the time for which they are available List ...
Shibaprasad's user avatar
6 votes
2 answers
260 views

How to partition a giant tour into feasible routes?

In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then ...
Kuifje's user avatar
  • 13.5k
1 vote
1 answer
108 views

How to construct LIFO constraints in Pickup and Delivery Problem

I am reading the following paper on the pick-up delivery problem with LIFO but ultimately failing to understand the LIFO constraint that the authors used. Here is the paper: Cherkesly, M., ...
mars's user avatar
  • 629
1 vote
0 answers
261 views

Problem of optimal solution generated with Pulp

I'm trying to use Pulp to solve VRP problem. Here is the model: ...
MAYA's user avatar
  • 129
1 vote
1 answer
678 views

TypeError: unsupported operand type(s) for *: 'IntVar' and 'float' in ortools [closed]

I am trying to implement a constraint as follows: ...
mufassir's user avatar
  • 211
2 votes
1 answer
206 views

Control load per trip in multi trip VRP in ORTools

I have implemented multitrip VRP in ortools (To be specific, solved CVRPTW with virtual depots). Maximum number of trips per vehicle is limited to 2. I want to put a hard constraint that load carried ...
mufassir's user avatar
  • 211
3 votes
0 answers
302 views

Or-tools : CVRP multiple time window with multiple location

I am using or-tools to solve a CVRP with multiple time window, and multiple location. Meaning that a customer can move during the day. I can't achieve to add constraint like if i deliver the customer ...
Cyprien's user avatar
  • 31
2 votes
1 answer
254 views

Implementing subtour constraints to a VRP in python

Hi I have a problem related to the vehicle routing problem, where I want to implement the subtour constraints $\sum_{(i,j)\in S} x_{ij} \leq \lvert S \rvert - r(S), \: \forall S \subseteq N, S > 2$ ...
Magnus M's user avatar