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
4
votes
1answer
130 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 ...
4
votes
0answers
84 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
1answer
74 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 ...
2
votes
1answer
68 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
1answer
290 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
1answer
186 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
5answers
562 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
1answer
82 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 ...
8
votes
2answers
234 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
4answers
418 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
1answer
154 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, ...
1
vote
0answers
36 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
0answers
101 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
0answers
70 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
1answer
171 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
2answers
175 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 ...
2
votes
2answers
134 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: ...
2
votes
2answers
186 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 ...
4
votes
1answer
70 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 ...
3
votes
1answer
55 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 ...
1
vote
1answer
110 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 ...
4
votes
1answer
122 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 ...
1
vote
1answer
176 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 ...
5
votes
1answer
113 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 ...
2
votes
3answers
511 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 ...
4
votes
1answer
152 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 ...
1
vote
1answer
112 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, ..., ...
4
votes
1answer
167 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.
2
votes
1answer
157 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. ...
4
votes
1answer
86 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: ...
2
votes
0answers
191 views

modify pickup and delivery problem to only delivery scenario in google OR-tools

I am using Google OR Tools for solving the capacitated vehicle routing problem.I want to implement optimization solution for delivery problem.For example there is one storage location which load all ...
7
votes
0answers
390 views

OR-TOOLS : delivery node with multiple possible pickup nodes

I am using ortools to model a VRP with pickup and delivery constraints, where pickups can be done at different nodes. For example, if node A has a demand, it must be picked at node B or C. Here is how ...
6
votes
1answer
223 views

OR-TOOLS : is it possible to partially fulfill a demand?

I am working on a vehicle routing problem with or-tools. Is it possible to partially fulfill a demand? I know it is possible to drop nodes with the disjunction constraints. But in this case, a node is ...
2
votes
1answer
188 views

VRPTW implementation

Does anybody have an example of the vehicle routing problem with time windows (VRPTW), implemented on Python with CPLEX library, AMPL, or MiniZinc? So far I've looked into ...
6
votes
0answers
61 views

Estimating multistop routing costs

In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints. An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
1
vote
0answers
102 views

How to develop a vehicle routing optimization package? [closed]

I would like to know how vehicle routing software optimizes routes? In demos of this software, they provide the optimal (or a good) route in just a few seconds or minutes with several nodes (maybe 50 ...
4
votes
1answer
178 views

How to represent time window as constraint in a vehicle routing problem

Hi I am trying to solve a vehicle routing problem using Tabu search, I have successfully completed implementation of constraints for CVRP by giving penalties to objective function , how do I implement ...
6
votes
2answers
421 views

Branch and Price Algorithm

Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP. In the literature, I haven'...
4
votes
1answer
190 views

Column Generation algorithm

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
6
votes
1answer
174 views

Asymmetric vehicle routing benchmark instances

Is there a standard set of asymmetric capacitated vehicle routing problem (ACVRP) benchmark instances similar to CVRP (http://vrp.galgos.inf.puc-rio.br/index.php/en/)? The only thing I found were a ...
5
votes
0answers
94 views

Column generation approach for CVRP

I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about ...
3
votes
1answer
132 views

A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet

I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
5
votes
1answer
247 views

Column Generation algorithm for vehicle routing problem

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
5
votes
0answers
90 views

Are there any good models for min-max vehicle routing problem?

I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
7
votes
1answer
103 views

CVRP with vehicles blocking each other

I have a standard CVRPTW (capacitated vehicle routing problem with time windows). The instance is given by a (not complete) graph $G$ with weighted $w$ directed edges $e \in E$, and I have a limited ...
4
votes
1answer
174 views

Is it possible to solve VRP using OR-Tools CpModel, instead of RoutingModel?

Is it possible to solve VRP using OR-Tools CpModel, instead of RoutingModel? I want to do synchronized VRP, which is combining vehicle routing and scheduling constraints
5
votes
2answers
294 views

Priority List Constraint

I used the Vehicle Routing Problem example that has the objective of minimizing total distance traveled for each vehicle. Suppose that each order to pick up for each vehicle at each node has a ...
2
votes
2answers
197 views

How to use tight upper and lower bounds to get to the optimal value via branch and bound?

I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour ...
1
vote
0answers
79 views

Fixed cost associated to SlackVar(waiting time cost) [CVRPTW]

I'm modeling a CVRPTW with some features: Each type of vehicle has a cost per km and a fixed cost per trip. To calculate these costs, I am using these methods for this: ...
4
votes
1answer
218 views

Adding a hard and soft upper bound constraint of number of locations to visit (VRP)

I went through the Vehicle Routing Problem example and was able to replicate it. On the example, there is a constraint added for vehicle maximum distance as shown below: ...