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
0 answers
56 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 ...
user avatar
  • 429
3 votes
2 answers
119 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 ...
user avatar
  • 133
5 votes
1 answer
149 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 ...
user avatar
2 votes
2 answers
80 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, ...
user avatar
  • 429
4 votes
2 answers
83 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: ...
user avatar
  • 41
8 votes
1 answer
179 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 ...
user avatar
7 votes
3 answers
300 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'...
user avatar
8 votes
3 answers
421 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 ...
user avatar
  • 10.1k
4 votes
3 answers
218 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 ...
user avatar
1 vote
1 answer
57 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 ...
user avatar
  • 117
2 votes
2 answers
149 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 ...
user avatar
1 vote
0 answers
41 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 ...
user avatar
  • 429
1 vote
1 answer
73 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, ...
user avatar
1 vote
1 answer
93 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 ...
user avatar
  • 429
2 votes
1 answer
80 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 ...
user avatar
2 votes
2 answers
137 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 ...
user avatar
  • 429
1 vote
0 answers
54 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 ...
user avatar
  • 533
3 votes
0 answers
130 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 ...
user avatar
  • 533
2 votes
1 answer
100 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 ...
user avatar
1 vote
1 answer
120 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 ...
user avatar
4 votes
1 answer
251 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 ...
user avatar
4 votes
0 answers
181 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:...
user avatar
2 votes
1 answer
109 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 ...
user avatar
  • 347
2 votes
1 answer
175 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 ...
user avatar
4 votes
1 answer
305 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?
user avatar
6 votes
1 answer
211 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 ...
user avatar
10 votes
5 answers
591 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 ...
user avatar
6 votes
1 answer
124 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 ...
user avatar
  • 659
8 votes
2 answers
377 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 ...
user avatar
5 votes
4 answers
450 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 ...
user avatar
2 votes
1 answer
459 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, ...
user avatar
  • 10.1k
1 vote
0 answers
38 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/...
user avatar
0 votes
0 answers
130 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 ...
user avatar
1 vote
0 answers
92 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 ...
user avatar
2 votes
1 answer
493 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$ ...
user avatar
5 votes
2 answers
205 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 ...
user avatar
  • 1,229
3 votes
2 answers
189 views

OR-Tools: Partial Solution ignored due to "unknown rate is too large"

With SetHint() from the OR-tools linear solver I am trying to pass a feasible solution to my problem. But I receive the following warning: ...
user avatar
  • 83
2 votes
2 answers
286 views

Trouble with optional nodes in a VRP model using Gurobi for python

I am currently working on a VRP problem where the vehicles are electric. This means that I have range restrictions, and charging stations as nodes which are optional to visit. In my model I have the ...
user avatar
  • 29
4 votes
1 answer
72 views

Clustering problem involving multidepots and customers requiring commodities located exclusively in an specific depot

I'm trying to solve a clustering problem that's similiar to a VRP Pickup and Delivery problem with multiple depots and customers. Each customer demands a commodity that is exclusively found on one ...
user avatar
3 votes
1 answer
61 views

How to assign task, resources to trips

In a scheduling problem I want to assign the resources to tasks, each task has earliest start date, latest start date and duration. Also each resource has fixed number of available hours in a day. The ...
user avatar
  • 101
1 vote
1 answer
124 views

Roulette mechanism with ALNS

I found in the literature that Adaptive Large Neighborhood Search (ALNS), which uses a roulette mechanism to select the best-performing operators, is the most efficient method. However, other ...
user avatar
  • 133
4 votes
1 answer
148 views

How to improve the solution in ALNS metaheuristic

I am solving the CVRP with Adaptive Large Neighborhood Search (ALNS) . I used the following construction operators: GreedyInsertion and ...
user avatar
  • 133
1 vote
1 answer
308 views

Why some decision variables don't get values in Cplex?

I use this code in the cplex and don't know why some decision variables don't get value, I attach my code below. I don't know my model is wrong or my code? I haven't error in the code but have some ...
user avatar
  • 55
5 votes
1 answer
139 views

Incomplete initial solution for capacitated vehicle routing problem

I am solving Capacitated Vehicle Routing Problem (CVRP) with Adaptive Large Neighborhood Search (ALNS) metaheuristic. I start my algorithm with a random initial solution, but the solution I get is ...
user avatar
  • 133
2 votes
3 answers
519 views

Random solution for capacitated vehcle routing problem (cvrp)

I'm currently solving the capacitated vehicle routing problem (cvrp) with the approached methods (metaheuristics). In order to do this I have to build a random initial solution. My question is when we ...
user avatar
4 votes
1 answer
169 views

Calculate the average of the objective function values ​resulting from metaheuristics after a defined number of executions

I am trying to solve the capacitated vehicle routing problem (CVRP) with the ALNS metaheuristic. To test the performance of my algorithm I run it 10 times and I want to calculate the average of the ...
user avatar
2 votes
1 answer
191 views

Difference between Solomon's problem instances

I am in the process of solving the VRP and I have a set of Solomon test instances to test my program. I actually found a test set with C101, C102, ..., ...
user avatar
4 votes
1 answer
195 views

VRP book recommendations

I am looking for a book recommendation on the VRP and variants. I am encountering VRP-like problems more and more in my work and would appreciate a reference.
user avatar
2 votes
1 answer
169 views

Working with large models

I am working with a variant of TSP, number of nodes that I need to test are in between 2500 to 3000 nodes, I am using docplex for modelling, I have a 8 gb Ram but it gets filled with only 400 nodes. ...
user avatar
  • 1,579
4 votes
1 answer
95 views

To calculate the time needed for a vacuum robot to cover whole area

A vacuum robot runs on randomized direction when it is operating in a room. I want to know how long it takes to fully cover the whole area (or at least most part of the area) with given information: ...
user avatar
  • 429