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.
129
questions
1
vote
2
answers
146
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 ...
- 11
1
vote
0
answers
67
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 ...
1
vote
0
answers
19
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 ...
- 133
1
vote
2
answers
92
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 ...
- 13
0
votes
0
answers
46
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 ...
- 189
3
votes
0
answers
56
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 ...
- 619
1
vote
1
answer
61
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 ...
- 23
2
votes
0
answers
44
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 ...
- 457
6
votes
2
answers
244
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 ...
- 12.3k
1
vote
1
answer
72
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., ...
- 619
1
vote
0
answers
121
views
Problem of optimal solution generated with Pulp
I'm trying to use Pulp to solve VRP problem. Here is the model:
...
- 111
1
vote
1
answer
503
views
TypeError: unsupported operand type(s) for *: 'IntVar' and 'float' in ortools [closed]
I am trying to implement a constraint as follows:
...
- 181
2
votes
1
answer
80
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 ...
- 181
3
votes
0
answers
150
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 ...
- 31
2
votes
1
answer
164
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$ ...
- 21
2
votes
1
answer
88
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 ...
- 145
2
votes
0
answers
52
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 ...
prajwalram8
3
votes
3
answers
301
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 ...
- 131
3
votes
0
answers
65
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 ...
- 207
3
votes
0
answers
111
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 ...
- 153
2
votes
1
answer
100
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 ...
- 207
1
vote
1
answer
84
views
What is the meaning of this multi commodity formulation VRP in LINGO
Can someone tell me what is the meaning of this multi commodity flow formulation that I got in LINGO ? I have the brief explanation about the model but don't quite understand the logic behind, here is ...
- 573
3
votes
1
answer
187
views
LocalSolver at 100% Gap
Can somebody help me with Localsolver? I have installed the academic license and want to solve Split Delivery VRP. I'm using the same model as seen in the website here and using the same instances too ...
- 573
3
votes
3
answers
307
views
Can I formulate a green vehicle routing problem with pyomo model then solve it with metaheuristics algorithms e.g. GA,HS rather than pyomo solver?
I want to use pyomo to formulate MILP problems in python such as Green Vehicle Routing Problem and others but use metaheuristics algorithms (GA, Harmony search, etc.) to solve those problems instead ...
1
vote
2
answers
397
views
Subtour elimination in SDVRP
I have the model below, based on this paper. It's a vehicle routing problem with split deliveries, i.e the locations/customers can be visited by multiple vehicles that share the demand at that vehicle....
- 207
2
votes
0
answers
67
views
Multi Commodity VRP Time Windows Paper
I have been wondering is there any paper that who discuss multi commodity with four index/indices like this formulation below:
$$
\begin{gathered}
\sum_{k} \sum_{c} F_{j, j, c, k}=1 \quad \forall j \\
...
- 573
2
votes
0
answers
56
views
Preprocessing Time Windows Width in Vehicle Routing Problem (VRP)
I think my model takes much time because the time windows width given the problem i want to solve.
Here is the time matrix:
...
- 573
8
votes
6
answers
536
views
Cannot Get Optimal Solution with 16 nodes of VRP with Time Windows
I have been wondering if my code is wrong or something. But why can't I get the optimality with only 16 nodes (I have clustered it so the max now becomes 16 from a total of 54 nodes)? My model was ...
- 573
0
votes
1
answer
59
views
What is the meaning of this math formulation?
I have been wondering what is the meaning of this sigma with delta negative or plus in there (if my read is correct).
$$
\sum_{i \in \Delta^{-}(j)} x_{i j k}-\sum_{i \in \Delta^{+}(j)} x_{j i k}=0 \...
- 573
2
votes
0
answers
40
views
Help with the KKT conditions of a SPT problem
Could anyone help me with the KKT conditions of my problem? The different sums and sets confuse me more than a little.
$$
\min_x \sum_{a \in A^1} p_a^1 X_a + \sum_{a \in A^2} p_a^2 X_a + \sum_{a \in A^...
- 423
6
votes
2
answers
341
views
Metaheuristics vs Column generation for VRP
I am solving a vrp and its variants (pick up drop off, milk-run problem) using genetic algorithms. The issue that I am getting with the genetic algorithm is the randomness associated with the ...
- 619
1
vote
0
answers
99
views
Set Partitioning Formulation of PDPTW
I am studying a paper on a Pickup Dropoff Problem with Time Window (https://pubsonline.informs.org/doi/abs/10.1287/trsc.1090.0272 ). The three index formulation is straightforward. The formulation is ...
- 619
4
votes
2
answers
164
views
How does the VRPTW model ensure the arrival time at next station tightened?
In VRPTW problem, given
$[a_i, b_i]$: the time window for node $i$
$x_{ijk}$: a binary variable that represents that the vehicle $k$ travels from node $i$ to $j$ (yes 1 otherwise 0)
$s_i$: the ...
- 143
5
votes
1
answer
578
views
How does OR-Tools improve on an initial solution to CVRP?
I have an initial solution to a CVRP instance which I am setting as input to the solver. The solver as expected returns an improved solution. I have a few questions regarding the solver.
How does the ...
- 91
2
votes
2
answers
114
views
Pick up drop off problem on fixed / dynamic route
I am working on the following problem and was wondering if anyone can give me some insight.
There is a fixed route that a vehicle (V1) with a fixed capacity uses everyday to pickup orders from node 1, ...
- 619
4
votes
2
answers
93
views
How to bundle pairs of trips?
I have a database of real-time optional trip demands. Each with a load that needs to be delivered from a departure point to a destination:
...
- 41
9
votes
1
answer
253
views
Odd behavior in the branch bound and price algorithm with column generation
I have two questions on branch-bound-and-price.
Why does it sometimes fail? For instance, the paper by Dabia et al shows results where the proposed algorithm fails for some cases. The paper does not ...
7
votes
3
answers
331
views
TSPs and VRPs in real world
I have a CS background, I took some optional courses in Optimization.
I stumbled upon classic transport problems like TSP and VRP.
Maybe I am not familiar with the domain, but I think that there aren'...
- 71
8
votes
3
answers
494
views
How to tackle this VRP variant?
I am currently working on the following problem, which is a variation of a vehicle routing problem. I am looking for different ideas to tackle it.
Problem description
A set of nodes with a given ...
- 12.3k
4
votes
3
answers
231
views
VRPTW: is there a way to prevent waiting at a node before starting service?
In a typical VRPTW MIP formulation there are constraints that keep service at each node between node-specific lower and upper bounds. Using $x_{ijk}$ as a binary variable representing whether or not ...
- 41
1
vote
1
answer
65
views
Assignment Problems With More than One Class of Resource
I am working on a dispatch optimization problem in the trucking industry.
I have a first algorithm - a vehicle routing algorithm - that produces a series of tours.
I will need a second algorithm that ...
- 117
2
votes
2
answers
398
views
Modeling Refueling in Vehicle Routing Problem in OR-Tools
As the title suggests, I am working on a problem that pertains to single-vehicle routing, where certain vertices in V are not mandatory to be visited, but are ...
- 325
1
vote
0
answers
50
views
Pick Up Delivery with Time Window example/ Benchmark Problem [closed]
I am trying to solve a pick up and delivery problem with time window (variant of vehicle routing problem). Would anyone be able to direct me to some example problems with known solution or benchmark ...
- 619
1
vote
1
answer
270
views
How to stop the vehicle from reaching the depot in between the trip
Requirement overview:
The trip route can have the following type of task
Delivery only
Pickup only
Pickup from one location and deliver to another location
Condition: Once a trip starts from depot, ...
- 11
1
vote
1
answer
110
views
Genetic Algorithm
I am evaluating a genetic algorithm that was written for a vehicle routing problem with time windows. The problem was not solved with any exact method (or with any solver). I also do not know bound of ...
- 619
2
votes
1
answer
393
views
Minimize capacity of vehicles in VRP with OR Tools
I'm using Google's OR tools in Python to do some optimization in routing in a model where I need to pick just the bare minimum to satisfy a demand.
The situation is, let's say I need 100 units of the ...
4
votes
2
answers
350
views
Multiple Pick-Up Delivery Problem with Time Windows
I am learning pick-up drop-off problems (variant of vehicle routing problems) with time windows. My problem is as follows:
There are orders that need to to shipped from pickup locations to delivery ...
- 619
1
vote
0
answers
59
views
GENIUS (General Insertion (GENI) + Unstringing / Stringing (US) - Anyone familiar with the procedure? I have questions
I am currently trying to understand the concept of GENIUS.
It was a method devoloped to solve the tsp.
The first step seems logical to me:
GENI (construction phase): start of with an tour of 3 nodes ...
- 533
3
votes
0
answers
172
views
Good book to get familiar with the key concepts of Operations Research for a person which didn't enjoy a good math education in university?
I am currently reading research papers on optimization problems in logistics and struggle to understand the math notation. Any good beginner friendly books you would recommend?
This is the paper I ...
- 533
2
votes
1
answer
141
views
Number of paths in asymmetric capacitated vehicle routing problem
This seems like a natural question, but I was not able to find an answer. My question is this. Consider a CVRP where $n$ customers have to be serviced by $m$ vehicles on any given day. All the ...
