0
$\begingroup$

In most VRPs, we start from a set of fleets (homogeneous or heterogeneous) and a set of points to be served. Then there are other constraints that need to be taken care of.

I am looking for a heuristic that will generate this set of fleets given different serving points.

I have two major constraints:

  1. Tour length: It has to be less than a given time (typically 12-14 hrs)
  2. Demand

The tricky thing here is the tour length. So say, if my demand is 1000 kgs, and I have some fleets with a capacity of 1200 kgs, that doesn't mean those fleets will be able to serve the load. Because there may be one or more fleets that will have the tour length condition violated.

Is there any heuristic that helps to generate a set of feasible set of fleets?

Currently, I am doing this:

  1. Randomly select a set of fleets that has the capacity to serve the loads
  2. Do the VRP and calculate the tour length
  3. Replace the vehicle(s) for which the tour length exceeds the given limit with an equivalent set of smaller-sized vehicles
  4. Repeat 2&3 until the selected combination has all the feasible trips

Is there any other intelligent way?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What do you use behind "Do the VRP"? Why not use directly a solver that supports a heterogenous fleet? $\endgroup$
    – fontanf
    Jun 29 at 7:53

1 Answer 1

Reset to default
2
$\begingroup$

You could for example adapt the well known Clarke & Wright algorithm and only generate routes that meet all of the required constraints.

This is precisely what is done in the VRPy library. You can find the Clarke & Wright adaptation here, where optional constraints can be activated:

  • capacity constraints
  • maximum number of stops
  • maximum duration of tour
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, @Kuifje. This partially solves the problem. But say even in this case I will be starting with a set of demand points and a list of vehicles. Now I want to know what vehicle configuration I should start with, that can give me at least feasible solutions. One thing I can do is, do VRP through the VRPy, if there is infeasibility, add another vehicle. But I was thinking if there is any more intelligent way, other than doing iterative VRPs. $\endgroup$
    – Shibaprasadb
    Jun 30 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.