Heterogeneous fleet

[N-Wouda]

Partially discussed already in #5, but this issue focuses a bit more on the specifics. I would like to add support for a heterogeneous fleet of vehicles in the near term, because I need it for the prize-collecting VRP paper (#180). I'm thinking:

• A Vehicle object, like the current Client. This object minimally have a capacity member, but I can see other members pop-up in the near future (e.g., speed, availability, etc.)
• Each route corresponds to a vehicle. This is easy to do in the Route object in LocalSearch with a new member, but we need to be careful when shuffling routes (based on empty/non-empty and polar angle) so that this relationship isn't broken. I think we can do this on a case-by-case basis.

[N-Wouda]

@wouterkool I know you need some of this as well. My timeline (if I do it) for this is sometime early April. Do you need it before then, or is that OK?

[wouterkool]

My proposal would be to implement Route (or RouteData) instead of Vehicle (as it is more general ; it can be a bike as well) with:

• vehicleCapacity, to support heterogenous vehicle capacity in fleet
• depot (id of depot), to support multiple depots where each route is fixed to a depot (fixed fleet per depot)
• earliestStartTime/latestEndTime (currently this is implemented as the depot time window but potentially different routes could have different start/end times at the same depot)

Some things that should be considered:

• How do we represent the routes in Individual? I see three options:
  • No longer filter empty routes and sort by polar angle so the index corresponds to the route in ProblemData
  • Add an additional property route_indices or something like that to indicate indices in ProblemData to which routes correspond
  • Wrap each route (list of ints) in a class SolutionRoute (and rename Individual to Solution) which includes the list of stops, but also the route_idx. This could then potentially also implement some cached properties like distance, penalties etc. per route (the once currently in diagnostics.py. best in my opinion
• How do we handle moves involving empty routes in the local search?
  • Just leave as is (consider first empty route), accept it is suboptimal
  • Try all route empty routes (simple but possibly slow)
  • Intelligently try one empty route per 'route type', e.g. by grouping routes somehow, or assuming sorted routes and only doing the move if the empty route has different properties than the previous empty route
• Should we consider extra operators in the local search?
  • For example moving a complete route to a different vehicle type. This could potentially be implemented as two-opt involving two depot nodes (which we currently don't consider), but a dedicated implementation may be simpler/faster.

Combining everything in a single PR is rather large, but I'm not sure if we should merge multi-depot support to main without having the corresponding operators as well? Shall we set up a separate branch for this again? @N-Wouda

[N-Wouda]

The literature on heterogeneous fleet VRPs (HFVRPs) is fairly large. There is a bit of ambiguity in what "heterogeneous fleet" means, and many authors solve slightly different variants of the HFVRP. The vehicles are of different types, and each type has a particular capacity and cost. The costs can be split into two parts: a fixed cost that's incurred if the vehicle is used at all, and a dependent cost $c_{ij} = rt d{ij}$ that's basically a scalar multiple $r_t$ of the distance driven by vehicles of type $t$.

Máximo et al. (2022) present a few of these variants, also described by Penna et al. (2013):

1. HVRPFD, with limited fleet and fixed and dependent costs;
2. HVRPD, with limited fleet and dependent costs;
3. FSMFD, with unlimited fleet and fixed and dependent costs;
4. FSMF, with unlimited fleet and fixed costs;
5. FSMD, with unlimited fleet and dependent costs.

Much less is standardised when we go to HF with time windows. Some papers use durations that depend on the vehicle type, and minimise overall travel time. Others stick to costs based on distances. I suspect we might need to allow for both, letting users pass custom distance and duration scaling factors (or even matrices?) for each vehicle type.

[N-Wouda]

In terms of implementation/modelling, perhaps something like

struct VehicleType
{
    size_t amount;
    size_t capacity;
    cost_type fixedCost = 0;
    distance_type distanceScale = 1;
    duration_type durationScale = 1; 
};

and updating Route and Individual::Route to hold some notion of which vehicle type is currently assigned to the route?

[wouterkool]

Thanks for researching the literature, it make sense to consider this generally. I think we could separate 'general' support for heterogeneous vehicle types, and then we can seperately support:

• heterogeneous capacity
• heterogeneous cost
• mutli (heterogeneous) depot by pre-assigning routes to depots

See my earlier comment, I proposed a struct similar to yours and indeed we could consider cost in there as well. Still, my preference would be to call it RouteType which is more general than VehicleType.

[wouterkool]

Ok reconsidering this I think it makes sense to consider heterogeneous capacities and costs together, as it make little sense that different types of vehicles have the same costs. I think we should implement fixedCost/costPerVehicle and costPerDistance/costPerDistanceUnit.

Scaling the distances could achieve the same for now, but that would also make the distance in the route/solution statistics scaled and would affect things like max distance constraints if we'd implement them.

Regarding durations, I suggest we leave this for now as a 'speed factor' is unlikely to hold in general, heterogeneous duration matrices are much more involved and we do not support duration as part of the objective (yet) either.

[N-Wouda]

From what I understood from our meeting last week is that we were going to do multiple capacities, but leave the rest for now since it seemed overly complex.

[wouterkool]

From what I understood from our meeting last week is that we were going to do multiple capacities, but leave the rest for now since it seemed overly complex.

That is indeed what we discussed. However, on second thought, I think it makes much sense to at least support heterogeneous costs coefficients for heterogeneous capacities. We also discussed we would like to support duration as an objective, which means we need to weight between distance and duration anyway ; if we do so, given how I'm planning to implement this it's very little effort to support different weights per vehicle type. As I need it anyway I'll make a proposal and we can see if we want to merge it.

For heterogeneous speeds I agree that makes no sense and general heterogeneous distance/duration matrices are too complex, so I agree we should not implement those.

[N-Wouda]

For a paper revision Leon and I need at least the fixed cost part. That's independent from the distance calculations / dependent costs, so I think it can be implemented pretty easily. There should also be some benchmark instances for that setting.

At that point it's probably also a good idea to invest in a "swap vehicle type" route operator, since we do not currently have a good way of swapping vehicles. That'll become even more important as we add more vehicle-specific properties.

[N-Wouda]

This should work for evaluating distance/time warp changes in SwapRoutes, when we have multiple depots and both routes are non-empty:

    auto const &uVehicleType = data.vehicleType(U->vehicleType());
    auto const &vVehicleType = data.vehicleType(V->vehicleType());

    auto const uDepot = uVehicleType.depot;
    auto const vDepot = vVehicleType.depot;

    if (uDepot == vDepot)
        // Then the start and end depots are the same, so there are no changes
        // in distance or time warp, and we do not have to evaluate those.
        return deltaCost;

    // Changes in distance from and to the depot.
    auto const uDeltaDist = data.dist(vDepot, (*U->begin())->client())
                            + data.dist((*U->end())->client(), vDepot)
                            - data.dist(uDepot, (*U->begin())->client())
                            - data.dist((*U->end())->client(), uDepot);

    auto const vDeltaDist = data.dist(uDepot, (*V->begin())->client())
                            + data.dist((*V->end())->client(), uDepot)
                            - data.dist(vDepot, (*V->begin())->client())
                            - data.dist((*V->end())->client(), vDepot);

    deltaCost += static_cast<Cost>(uDeltaDist) + static_cast<Cost>(vDeltaDist);

    // Changes in time warp.
    auto const uTWS = TWS::merge(data.durationMatrix(),
                                 V->tws(0),
                                 U->twsBetween(1, U->size()),
                                 V->tws(V->size() + 1));

    deltaCost += costEvaluator.twPenalty(uTWS.totalTimeWarp());
    deltaCost -= costEvaluator.twPenalty(U->timeWarp());

    auto const vTWS = TWS::merge(data.durationMatrix(),
                                 U->tws(0),
                                 V->twsBetween(1, V->size()),
                                 U->tws(U->size() + 1));

    deltaCost += costEvaluator.twPenalty(vTWS.totalTimeWarp());
    deltaCost -= costEvaluator.twPenalty(V->timeWarp());

    return deltaCost;

I started writing this in #359, but felt it was out of place there since we do not yet support this case.

[N-Wouda]

I had a look at the HFVRP instances used in the AILS paper of Maximo et al. (referenced somewhere above in this thread). They're available here, but only in their basic form. Not with the HF-specific values or anything. Those are, as far as I can tell, added in by the program when the instances are loaded.

That's annoying. Additionally, the instances are rather small (the biggest has just 360 clients, with most far smaller). There might be better instances out there, but I haven't found them yet.

[leonlan]

With the introduction of #359 (and earlier #245), we can now solve FSMF (unlimited fleet and fixed costs). In Maximo et al. (2022) they use the Golden instances. Although these instances are not big, I’m going to do a quick check tomorrow if we can solve these instances to close to optimality. Also related to the comment above: the data of the instances can be found in Table 2 of the paper.

See Penna et al. (2019) for a more elaborate study of “rich” HFVRPs and benchmark instances. There’s an instance set (100 clients, 168 instances) for the FSMFTW by Liu and Shen (1999). Will also check that out.

[leonlan]

OK, I managed to generate the FSMFTW instances by Liu and Shen. I also did some benchmarking with 30 second time limits. The solutions are about 3% away from BKS, so that can still be improved quite a bit. I don't think this is too bad: the average runtime used by HGS in Vidal (2014) was 5 minutes with a processor with ~800 CPU passmark.

Will continue with this tomorrow.

[N-Wouda]

With such small runtimes one easy way to improve performance is tuning the parameters, because those are definitely not set right for that setting. If we run for the same (PassMark-adjusted) runtimes as Thibaut's 2014 paper, what gap do we get then?

More generally: what's the standard stopping criterion here?

[leonlan]

They used TimedNoImprovement(max_runtime=1800, max_iterations=5000). I can try running this later today.

[leonlan]

With the stopping criterion above, it's above 0.4% above BKS. Not too shabby, but I am also somewhat surprised that these instances are not trivially solved like the original Solomon instances. Maybe we need to allow swap routes to swap with empty routes too?

[leonlan]

FMSFTW instances in VRPLIB format using the extension described in https://github.com/PyVRP/PyVRP/issues/252#issuecomment-1709494652. FMSFTW.zip

I also checked Maximo et al.'s instances for FMSF, but they use Golden instances which are in size [20, 100]. The larger instances with 100-360 clients is only for other HF variants.

[mstf2077]

Hello, I'm trying PyVRP to solve CVRP and CVRPTW problems and found that PyVRP works fine for solving these problems. The program is well organized, tutorial and API documents are well prepared and they helped me to understand the program. Plotting is also fine. Thank you for sharing nice program!

Now I have an interest to apply PyVRP to solve real world problem which is the scheduling of trucks. In this problem, there are several types of truck which have different capacity. They depart from a depot, collect luggage from clients, and return back to the depot. So, I want to set different vehicle capacities in PyVRP.

In the README file, it says PyVRP supports heterogeneous feet VRP,

PyVRP is an open-source, state-of-the-art vehicle routing problem (VRP) solver. It currently supports VRPs with:

• Vehicles of different capacities, costs, and shift durations (heterogeneous fleet VRP);

Is this "heterogeneous fleet VRP" problem supported in the current stable version (v0.7.0) or development version? Though I read API document, I could not find the way to set different capacity values to vehicles. I appreciate if you can tell me the way to set different vehicle capacity values.

I appreciate for your contribution to develop and share nice program. I'm looking forward to further development of this program. Thank you.

[N-Wouda]

@mstf2077 I've moved your comment to #451 and posted an answer there!

[ge94lif]

Dear Niels and Leon,

I hope this message finds you well.

We are very interested in implementing the FSMFTW benchmark instances introduced by Liu and Shen(1999). Upon reviewing your repository, we noted that you successfully solved these instances, achieving favorable performance results.

We are currently attempting to replicate your achievements using the latest version of the main branch. However, we have encountered an issue wherein the program does not seem to be able to read the instances provided in the FSMTW.zip file. Specifically, it appears to assume the existence of only one type of vehicle, with the number of vehicles equal to the number of customers.

Considering the details of your implementation, we wonder whether you developed a solution for this problem within an alternative branch or a development version of the program.

Your insights and guidance on this matter would be immensely appreciated.

We sincerely thank you for your invaluable contributions to the development community and any assistance you can provide.

Kind regards, Maria Rodriguez

[N-Wouda]

@leonlan since you did the work to get those instances to run, could you comment on the how? :-)

[N-Wouda]

After that I think we can close this issue. Additional attributes for the VehicleType can be discussed in new issues, and variable distance/duration matrices per VehicleType (the last bit that keeps this issue open) is covered in #475.

[leonlan]

Hi Maria @ge94lif!

Indeed, the FSMFTW instances were developed on an old branch that is no longer available. Instead, see the zip attached to this message. This contains the instance generator, the instances, and a new read.py file that can be used to read these instances. See the README for more details - if you follow those instructions then it should be possible to solve FSMFTW instances with PyVRP on the current main.

Let me know if it works!

(Note that these data and results were experimental, so I haven't verified them in detail. Make sure you do that before drawing conclusions from the results :-))

FSMFTW.zip

[ge94lif]

Hi Leon @leonlan!

Thank you very much for your prompt response and for providing me with all the required information for setting up the instances.

Upon cloning the specified commit at https://github.com/PyVRP/PyVRP/tree/d68e3aa7044a3fce8ec0dcfd7da1751710e1a9d3, I proceeded to update the pyvrp/read.py file with the version you sent me. However, upon attempting to run an instance—such as "RC208a.vrp"—I encountered the errors illustrated in the attached images.

It seems like there may be an issue with the data being passed to the VehicleType constructor. Specifically, it appears that the "capacity" argument must be an integer, whereas it is passed as an array in the current code.

Thanks in advance for your support.

[leonlan]

@ge94lif Could you show me the full code that you are using? I'm not able to reproduce this. On the given commit and changed read.py, I can successfully run this on the command line:

poetry run pyvrp FSMFTW/FSMFTW/RC208a.vrp --seed 0 --max_runtime 1

[ge94lif]

@leonlan Yes, this is my test code:

from pyvrp import Model, read
from pyvrp.stop import MaxIterations, MaxRuntime
from vrplib import read_solution

INSTANCE = read("/Users/maferodriguezc/anaconda3/lib/python3.10/site-packages/PyVRP/instances/FSMFTW/RC208a.vrp",
                instance_format="vrplib",
                round_func="trunc1",
                )

BKS = read_solution("/Users/maferodriguezc/vrp/input_data/solomon/solution/RC208.sol")

print("Num of vehicle types: "+str(INSTANCE.num_vehicle_types))
print("Num of vehicles: "+str(INSTANCE.num_vehicles))
print("Num of clients: "+str(INSTANCE.num_clients))

model = Model.from_data(INSTANCE)
result = model.solve(stop=MaxIterations(5000))
print(result)

print("Fixed vehcile cost:" +str(result.best.fixed_vehicle_cost()))
routes = result.best.get_routes()

for r in routes:
    print("the vehicle type of the route is: "+str(r.vehicle_type()))
    print("the demand of the route is: " + str(r.demand()))
    print(str(r.has_excess_load()))

cost = result.cost() / 10
gap = 100 * (cost - BKS["cost"]) / BKS["cost"]
print(f"Found a solution with cost: {cost}.")
print(f"This is {gap:.1f}% worse than the optimal solution,", end=" ")
print(f"which is {BKS['cost']}.")

[leonlan]

@ge94lif I ran your code successfully. Here are some things to check:

• Did you replace the contents of the read.py file with the one that I have provided in the zip?
• Did you build PyVRP locally on the given commit? That is, have you run the command poetry install or poetry run python build_extensions.py?
  • Related: are you using a virtual environment in which you ran the command pip install pyvrp? I suspect you are using a pip-installed version of PyVRP because the error message fits this scenario.
  • If you did not build PyVRP locally, you can follow these steps: https://pyvrp.readthedocs.io/en/latest/dev/contributing.html#contributing up to section "Building the Python extensions."

[N-Wouda]

@ge94lif have @leonlan's comments helped you solve your problem?

[ge94lif]

Hi @leonlan and @N-Wouda,

Thank you so much for your support! I managed to run the instances successfully. I replaced the contents of the read.py file with the one you provided in the zip, and I also built PyVRP locally, as you suggested. I appreciate your guidance on using a virtual environment.

I will proceed to delve deeper into the results and compare them with the benchmarking data.

Best regards, Maria