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
51 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
67 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
111 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
  • 125
0 votes
0 answers
35 views

Capacited vehicle routing problem with heterogeneous fleet

This question is related to this post where I was trying to understand how to formulate the CVRP based on flow formulation to eliminate sub-tours. Capacited Vehicle Routing Problem with flow ...
MAYA's user avatar
  • 125
1 vote
2 answers
114 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
  • 125
0 votes
2 answers
156 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
  • 125
1 vote
1 answer
69 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
  • 201
4 votes
1 answer
144 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
99 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
77 views

Validity of a VRP formulation

A delivery company is operating in Virginia and has a fleet of trucks that are used to deliver groceries from supermarkets to consumers. The company delivers orders and operates its fleet for one ...
talkandtalkers's user avatar
0 votes
0 answers
62 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
89 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
77 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
108 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
138 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
105 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
92 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
88 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
147 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
35 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
  • 632
2 votes
1 answer
82 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
  • 521
4 votes
2 answers
68 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
43 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
55 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
60 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
65 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
136 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
62 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
455 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
164 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
68 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
27 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
109 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
57 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
65 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
73 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
49 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
255 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.2k
1 vote
1 answer
88 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
217 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
  • 125
1 vote
1 answer
632 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
  • 201
2 votes
1 answer
140 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
  • 201
3 votes
0 answers
273 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
225 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
2 votes
1 answer
99 views

Modify the network model to accommodate multiple vehicles

Given a directed network (or graph) $G = (V,E)$ with each edge $e_{ij}$ having a non-negative cost as the travel time from $i$ to $j$. Each node has an associated demand $d_i$. If the demand is ...
endeavor's user avatar
  • 145
2 votes
0 answers
54 views

Optimizing personnel allocation within a fixed period

I am working on an operations optimization problem and am describing the problem below. At first glance, it seems like a mix of vehicle route optimization and a scheduling problem. The expected ...
user avatar
3 votes
3 answers
326 views

Determining the problem type - Vehicle Routing - Task assignment

I want to figure out what problem I'm dealing with so I can move in the right direction of research. I'm still at the very beginning of formulating the problem. What I've done so far is figure out ...
Pascal's user avatar
  • 131
3 votes
0 answers
67 views

How can I use a local search meta heuristic after completing construction heuristic?

I'm investigating how I can combine a construction heuristic and a local search metaheuristic to quickly solve Capacitated Split Delivery Veichle Routing Problem (CSDVRP). The construction heuristic ...
Parseval's user avatar
  • 207
3 votes
0 answers
121 views

TSP-PD with time constraints between pickups and deliveries

Has anyone ever encountered the following variation of TSP? You have a TSP with pickups and deliveries, and in addition, for each pickup-delivery pair $(i,j)$, you have a constraint that the time you ...
Kathryn Twomey's user avatar
2 votes
1 answer
106 views

Construction heuristic for SDCVRP

I'm not sure how I should formulate this question as precisely as possible but at the same time retaining as much specific information as possible but I'll have a go. I have implemented a (Split ...
Parseval's user avatar
  • 207