When we use branch, price and cut method to solve VRPTW problems, the objectives is always:

  1. minimize the total distance, or
  2. minimize the sum of distance-related variable cost and truck-related fixed cost

But in reality, it's common that we want consider the working time related cost, which includes driving and waiting.

Therefore, except heuristics, do we have any good ways to consider time cost in BPC or other exact methods?

My understanding is that it should be very difficult since we can not deduce strong dominance rules to eliminate labels safely.

  • $\begingroup$ Can you elaborate on why dominance is an issue? $\endgroup$
    – gmn
    Apr 16, 2023 at 14:53
  • $\begingroup$ Given two labels $L_1, L_2$ on the same node, we would say $L_1$ dominates $L_2$ if: 1) $L_1.cumulativeTime \leq L_2.cumulativeTime$ 2) $L_1.reducedCost \leq L_2.reducedCost$ 3)$L_1.load \leq L_2.load$ 4) $L_1.visitedCustomers \subset L_2.visitedCustomers$. But if we consider the waiting cost, the first condition may not holds, since more left time resource may also means higher waiting cost. $\endgroup$ Apr 17, 2023 at 5:49
  • $\begingroup$ Do you have a specific VRP version in mind? Preferably a reference to a paper introducing the problem? $\endgroup$
    – gmn
    Apr 17, 2023 at 12:04
  • $\begingroup$ Actually I don't have one. I'm just wondering the possibility to include (waiting) time cost in objective function for VRPTW using exact method. Although we could find some researches on minimize the trip duration with exact method, and some others about minimize trip cost with heuristics. $\endgroup$ Apr 18, 2023 at 1:03


Your Answer

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

Browse other questions tagged or ask your own question.