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
5
votes
1answer
53 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|)$ because the most complex ...
8
votes
2answers
206 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
404 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
116 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
93 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
60 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
106 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
166 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
107 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
135 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
69 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
52 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
107 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
120 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
125 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
107 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
507 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
141 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
91 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, ..., ...
3
votes
1answer
152 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
156 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
82 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
178 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
347 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
210 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
172 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
58 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
98 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
131 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
401 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
184 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
171 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
88 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
125 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
219 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
84 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
102 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
161 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
245 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
184 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
71 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
177 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: ...
5
votes
3answers
209 views

Problem with binary decision variable constraints in VRP

I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable: ...
6
votes
1answer
278 views

Advanced Heuristics for MIP vehicle routing problem in PuLP

I am currently trying to speed up an MIP. An approach I was considering was to implement a cut callback heuristic with PuLP (one which rounds relaxed integer variables greater than .9 to 1). ...
4
votes
2answers
139 views

VRP app as a Minimum Viable Product

In this post, Geoffrey De Smet and EhsanK pointed out the opportunities of VRP variants (e.g. mixed pick up and deliveries). If I want to build a Minimum Viable Product (software as a service app). ...
2
votes
0answers
112 views

Montoya et al. 2017 benchmark Results

I am testing Montoya et al. 2017 dataset and trying to replicate the Result from this paper The electric vehicle routing problem with capacitated charging stations. I am unable to replicate the exact ...
4
votes
1answer
153 views

VRP benchmark instances with charging stations

Are there any benchmark instances for VRP with charging stations? I also have various delivery points with charging stations in the city(Multiple Vehicles). How can I compare my formulation?
4
votes
1answer
309 views

Solving vehicle routing problem in java

I am trying to solve vehicle routing problem in java and I am looking for libraries for the same. I did a POC using google or-tools and it seems to be solving all my use cases. I would like to know if ...
6
votes
1answer
538 views

Solution time out for VRPTW in or-tools

I am experimenting around with or-tools and somehow I can't get a solution for the VRPTW problem for any of the instances I have tested from Gehring & Homberger ...