9

Being a good or bad approach will depend on several factors, for example: the size of the instances time available to find a solution (this tends to be an important matter in vehicle routing applications) computing power what level of solution quality qualifies as good enough See this work by Yu, Nagarajan and Shen on the minimum makespan VRP with ...


7

Let $d_i$ be the demand for customer $i\in N$, let $V=\{1,\dots,K\}$ be the set of vehicles, and let $P$ be the set of columns, where each column corresponds to a feasible subtour starting from the depot, with arc variables $x_{i,j}$ and node variables $y_i$. Let $z$ be the makespan. The master problem over $z$ and $\lambda$ is as follows, with dual ...


7

If there is one book to know about VRPs, it is: "Vehicle Routing: Problems, Methods, and Applications, Second Edition" (Paolo Toth and Daniele Vigo, 2014)


7

I don't know if a closed form solution is achievable. Assuming you can quantify how the robot selects its next direction when it hits a boundary (uniform over the entire circle, uniform over directions not within some angle of its last direction, some nonuniform distribution, ...), you could fairly easily build a simulation model (starting with an empty room ...


7

Usually such statements mean that you should device a construction heuristic, which relies on some level of randomness. That is, if you run your construction procedure twice you should not (necessarily) get the same solution. I would in most cases, if not stated explicitly, expect the solution to be feasible to the problem (in your case it should probably ...


7

"Random solution" means the decision variables are chosen randomly. It does not usually mean ignoring feasibility constraints. So, in the case of CVRP, it would mean choosing the cities for a given route, as well as their sequence on the route, randomly. There are various ways to deal with the capacity constraint -- for example, if the next ...


6

There are multiple ways you can analyze and compare the results of heuristics/randomized search procedures. Report the average, best and worst Report the average, and standard deviation Graphically represent the results as a boxplot. When computing the average, you need to be careful when there are instances that could not be solved by the heuristic. This ...


6

Crossposted from: Stack Overflow The idea is to create another dimension ('visit') that is incremented by 1 on each visit. Then use SetCumulVarSoftUpperBound on the cumul variable of that dimension at the end of each route.


6

Before implementing anything, you need to understand the equations. A good approach is to think in terms of resources. When handling capacity constraints, you are dealing with a load resource which is limited to the vehicle's capacity. When dealing with constraints linked to time, you need an extra resource for this. Each of these resources can be delt with ...


6

Take a look at VRP REP's, filtered on ACVRP datasets. That listing includes my "Belgium" VRP datasets on on VRP REP (the most popular download on VRP REP) which contain asymmetric CVRP datasets. Look for the road-km and road-time variants in the files of that zip. The "air" variants are symmetric. It has variants with one depot and ...


5

Note that (as is asserted in the cited tutorial): The cost of a route is the addition of the arcs that compose it: $c_k = \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij}$ Relate $a_{ik}$ ($r_k$ visits customer $i$) with $b_{ijk}$ (route $k$ uses arc $(i,j)$): $a_{ik} = \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk}$ And the conditions (22) and (23) are equivalent ...


5

If I understand your problem correctly, you have a standard CVRP and a second (soft) objective. You are therefore in the wonderful world of multi-objective optimization. Typically what you do is try to turn this problem into a problem with a well defined optimal solution. There are some ways to do this: lexicographical ordering of objectives (Cplex calls ...


5

If I understood your problem correctly, then the only difference with the initial version (without the train) is that the time function is not additive. For example, lets say the train passes through node $j$ at (given) time $t_j$, and you are computing a path $p$ whose last node is $i$. The total accumulated time on this path is denoted by $\tau_p(i)$. $\...


5

There is no problem in starting your ALNS with an infeasible (what you call "incomplete") solution. ALNS consists of destroying a part of the solution and then repairing it, at each iteration. Generally, destroying is done by removing a number of tours in the incumbent solution. But you can adapt the method by selecting a number of tours plus some ...


5

Altough I agree with the other answers, I think its worth mentioning that a random initial solution does not have to be feasible. When using (meta)heuristics, it is often the case that infeasible solutions are used in the search space, while the number of conflicts (the number of times a constraint is violated) is minimized in the cost function. For example, ...


5

VRPy (v0.3.0) now supports this option : all you have to do is set the minimize_global_span option to True when instantiating the VehicleRoutingProblem object: prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True) prob.solve() Of course, your graph $G$ has to be well defined in the first place. The formulation proposed by @RobPratt is ...


4

You can split the demand in two visits. You will need to duplicate the node in two, and add a disjunction on each visit.


4

your model is not feasible and that is why you get no solution. if you comment //forall(i in cD,j in DI,t in T:t==2, f in F)cb10:recievetime[i][t]+(time[i][j]+servicetime[j][t])*K[i][j][f]-Tmax*(1-K[i][j][f])<=recievetime[j][t]; then you ll get some conflicts and relaxations like 72 [0,Infinity] [-6,Infinity] delta[1][2] 72 [0,Infinity] [-10,...


4

The roulette selection mechanism is a kind of choice function. Thus, the question is not well stated. What is the other choice function you consider against roulette selection? The roulette selection is a randomized, possibly biased, choice function. Randomization is an important ingredient of the efficiency of neighborhood search approaches in combinatorial ...


4

These constraints should be treated in a "dynamic fashion". First you ignore them. Then you check whether your solution satisfies them or not (possibly some timing in your solution should be changed without changing routes themselves). I suppose that most of the time these constraints will be satisfied. If not, you need to find a minimal subset of ...


4

The answer is yes. Is it worthwhile ? it depends. If you just want to have two persons visit the same virtual place (2 duplicated nodes) at the same time, you can force the time cumul var to be equal when using the routing library. This will probably more efficient than the CP-SAT VRP code as the routing library is highly tuned. If you want more complex ...


4

In my experience when solving Vehicle Routing with time windows in the industry, with one case handling 50 000+ vehicles and 100 000+ visits per day as well as many other cases with lower numbers, all running in production, I notice that: The problem is often (un)naturally partitioned, due to Conway's law. In the 50K+ vehicles case, each vehicle and visit ...


4

Welcome to OR.SE. It is not easy to enter into your problem and your model. You have modeled your problem in MILP, with each edge represented as a 0-1 variable. There are different possible formulations. All will be tedious to implement, even more if you have many constraints to implement. To make it easier and more scalable, we suggest you follow a ...


3

We (Thibaut Vidal, Daniele Vigo, Michael Schneider, and I) just released a preprint on decomposition methods for Vehicle Routing heuristics. Clustering is one such family of methods and we try different types of clustering in our computational experiments. Indeed, it works very well, as long as: The clusters are based on some existing high-quality solution. ...


3

I make a commercial vehicle routing solver for both dynamic and static problems (see https://odllive.com), and so I can offer a bit of industry insight into this question. Using heuristics, metaheuristics including things like clever splitting of the problem, you can get to much larger problem sizes. This doesn't mean of-course that you're getting optimal ...


3

We encourage you to look at the code of jsprit, the open-source Java vehicle routing library. The jsprit approach is based on a "ruin & recreate" heuristic, also known as Adaptive Large Neighborhood Search (ALNS). The operators can be found here in the folders "ruin" and "recreate" respectively.


3

Please have a look at our answer to a previous post about modeling and solving TSP by using LocalSolver: How to model a TSP where the salesman can choose between flight, train and bus for every single connection? Your problem can be modeled differently from the one you proposed above by following a list-based modeling approach instead of the classical ...


3

This is a tough problem indeed, but I am not sure about the "extremely NP-hard" part :). All problems which are NP-hard are...very hard. This looks like a multi-commodity flow problem, one commodity per depot. It is natural to decompose such a problem as follows. For each customer $v\in V$, for each commodity $k\in K$ we assume that the demand $D_{...


3

In addition to @LocalSolver's answer, I believe you can solve your problem relatively easily with the or-tools routing library (free and open source). At its core, this library solves a TSP, over which you can add constraints with a resource based logic. For example, the load on a vehicle is a resource, this resource is incremented when visiting a node, and ...


3

Try: SetSolverSpecificParametersAsString("heuristics/completesol/maxunknownrate = 0.9") References: SCIP params SetSolverSpecificParametersAsString usage


Only top voted, non community-wiki answers of a minimum length are eligible