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
3 votes
3 answers
260 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
58 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
93 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 ...
2 votes
1 answer
85 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
57 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 ...
  • 513
3 votes
1 answer
130 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 ...
  • 513
3 votes
2 answers
92 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
194 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
64 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 \\ ...
  • 513
2 votes
0 answers
50 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: ...
  • 513
8 votes
6 answers
391 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 ...
  • 513
0 votes
1 answer
58 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 \...
  • 513
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^...
  • 403
6 votes
2 answers
245 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 ...
  • 499
1 vote
0 answers
75 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 ...
  • 499
4 votes
2 answers
147 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
286 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 ...
2 votes
2 answers
89 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, ...
  • 499
4 votes
2 answers
85 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
209 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
309 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'...
8 votes
3 answers
442 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 ...
  • 10.9k
4 votes
3 answers
221 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 ...
1 vote
1 answer
58 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
234 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 ...
1 vote
0 answers
43 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 ...
  • 499
1 vote
1 answer
133 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, ...
1 vote
1 answer
98 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 ...
  • 499
2 votes
1 answer
210 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 ...
2 votes
2 answers
220 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 ...
  • 499
1 vote
0 answers
55 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 ...
  • 543
3 votes
0 answers
143 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 ...
  • 543
2 votes
1 answer
108 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 ...
1 vote
1 answer
190 views

Tuples OPL in VRP

I am trying to build a constraint of the form x[i j] +x[j i] <y[i][j] where x is a decision variable if arc ...
4 votes
1 answer
322 views

Is Google's OR-tools for professional work? Specially VRP module [closed]

So I've been given at work a project which consist on finding optimal pathing for trucks in certain custom scenarios. When I discovered this tool I thought it worked wonders for what I understood the ...
5 votes
0 answers
270 views

Announcing OptaPy - a new open source constraint solver for Python (feedback welcome)

[Not sure if this counts as a proper question, but I've seen a few similar "new solver" announcements in the past, so I 'll take my chances.] A new constraint solver for Python has been born:...
2 votes
1 answer
150 views

A lexicographic objective function

I am trying to solve a multi-objective vehicle routing problem, I want to implement a lexicographic objective function, I have already defined a function for each objective. if someone has an idea of ...
  • 377
2 votes
1 answer
260 views

Adapting a cluster-first-route-second approach for VRP with heterogenous fleet

I have the following data: A fixed depot/facility location Dropping points with demands List of available vehicles (heterogeneous fleets) What I am trying to do is, given the list of vehicles and ...
4 votes
1 answer
313 views

Complexity of navigation with google maps

I was wondering what complexity a simple start-destination task in a routing software would have. Knowing the shortest path problem, it should be in P. Is there anything I am missing?
6 votes
1 answer
220 views

How to cope with the rigidity of solutions?

Consider the following problem of Technician Routing and Scheduling Problem. We have: A set of customers where each customer needs the intervention of a technician to do some job. Each customer has a ...
10 votes
5 answers
601 views

What is the state-of-art (in industry and academy) of this scheduling + routing problem?

I have a startup idea and I am coming from a CS background. The startup tries to solve the following problem. A company having a set of employees that needs to visit several "customers" each ...
6 votes
1 answer
161 views

In which time complexity operates the Savings algorithm for the TSP?

In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in $\mathcal O(|V|\log|V|)$ with V as vertex/node ...
  • 659
8 votes
2 answers
482 views

VRP through constraint programming

I am with a problem that consists of determining whether a VRP instance is feasible, this question is a continuation of an older thread. In order to do it, I was thinking of using Constraint ...
5 votes
4 answers
486 views

Solving Capacitated VRP with multiple various sized vehicles

I am looking to form a Capacitated VRP problem like this: I have 40,000 dropping locations with Demands of each point available I have 5-6 types of vehicles available with different capacities and ...
2 votes
1 answer
523 views

How to compute the minimum number of vehicles required

I am trying to solve the following problem: I have a set of $N$ requests that must be processed by vehicles. I do not know the locations of these requests. Requests can be processed by a same vehicle, ...
  • 10.9k
1 vote
0 answers
39 views

Constraint formation help

I am implementing a quay crane optimization model. The objective is to minimize the loading time. Inputs to the model are $I=$ number of nodes $K =$ number of cranes $z_k =$ crane speed in meter/...
0 votes
0 answers
139 views

Check VRP instance is feasibility

Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
1 vote
0 answers
98 views

Multiple conditions in indicator constraint of Gurobi

I'm working on a vehicle routing problem, in which a vehicle need to pick up amounts of things in some nodes. I'm trying to solve it by Gurobi optimizer. Except for meeting the time windows of each ...
2 votes
1 answer
678 views

Problem with vehicle routing problem in Gurobi Python

I have a vehicle routing problem solved by linear programming, but I'm confused about the constraints (see the model in figure 1). In the model, $u$ and $x$ are decision variables, and we set node $0$ ...
5 votes
2 answers
220 views

Asymmetric time-constrained capacitated vehicle routing problem

I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4). The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent ...
  • 1,229