2
$\begingroup$

I am working on the following problem and was wondering if anyone can give me some insight.

There is a fixed route that a vehicle (V1) with a fixed capacity uses everyday to pickup orders from node 1, 2, and 3 and deliver at node 4. However occasionally the pickup demand on one of the pickup is so high that V1 cannot pickup those orders. For example, as shown in Figure 1, the pickup demand at node 1, 2, and 3 are 25%, 65%, 25% of the capacity of the vehicle. V1 can only pick up order from node 1, and node 2 as it filles up 90% of its capacity. So, it skips node 3, and directly go to node 4 to deliver the items it picked up from node 1 and 2. Another vehicle needs to be sent to node 3 to pick up and deliver at 4.

Is there any known way to model and solve it? If you worked on something similar or read any related paper, would you please share?

Example Problem Description

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ We need more info. Are all trucks the same size? Can an order be split? For instance, can V1 pick up 40% of the order at node 3 (filling V1) and leave the other 60% (15% of truckload) for V2? Critically, what would your objective function look like? Would you minimize number of trucks used, number of stops made, total distance driven or something else? $\endgroup$
    – prubin ♦
    Apr 1, 2022 at 16:08
  • $\begingroup$ Hi @prubin, thanks so much for your comment. For now, I am assuming homogenous trucks and orders can not be split. The objective function will just be minimizatin of cost of routing ($ value of miles traveled), fixed cost of hiring a truck, stop off charge per stops. $\endgroup$
    – mars
    Apr 4, 2022 at 4:23
  • $\begingroup$ In that case I would go with Abbas Omidi's suggestion of a bin packing model, where the "bins" are predefined routes (each route a sequence of stops for one van, with cost equal to the sum of hiring, mileage and stop off charges). If there are too many possible routes to precompute, you can look at a branch-and-price approach or a heuristic approach where you generate new routes on the fly. $\endgroup$
    – prubin ♦
    Apr 4, 2022 at 15:55

2 Answers 2

Reset to default
2
$\begingroup$

If the routes are fixed and pre-defined, the problem can be reduced to a container loading problem or a variant of a bin-packing problem. In both cases, the orders might be split and assigned to the vehicle W.R.T vehicles capacity. Also, this makes flexible loading capacity.

Please, be aware that if the routes also need to be optimized, the problem is in the class of VRP variants.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you give any specific example of using bin-packing on pre-defined routes? $\endgroup$
    – mars
    Apr 4, 2022 at 4:16
  • $\begingroup$ @mars, please, suppose the given demands as items and each vehicle as a bin. Even you are being able to assign items partially or vehicle flexible capacity as what you want. I hope this would be helpful. $\endgroup$
    – A.Omidi
    Apr 4, 2022 at 7:45
  • $\begingroup$ yes, it does. Thanks so much! $\endgroup$
    – mars
    Apr 4, 2022 at 12:01
1
$\begingroup$

You'd model it by biasing the optimiser's cost model, so it's cheaper for the normal vehicle to serve these nodes, and in the normal sequence. e.g. the cost of assigning node 3 to v1 is 0, but assigning node 3 to v2 instead costs 100. In the literature this is sometimes called 'affinities'. I would suggest you also start optimising from an initial solution that has the normal routes, and so the optimiser just adjusts them as needed if they're infeasible. I'm not sure whether the open source solvers like jsprit, OR tools would support all this. We support this in our commercial ODL Live optimiser, by overriding the cost of a stop for certain vehicles, adding additional costs to a stop based on what the preceding stop was, and starting optimisation from an initial (and potentially infeasible) solution.

Improve this answer
$\endgroup$

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.