Evaluating the trade-off between cost and service-oriented objectives in routing and scheduling problems

Abstract

In many routing and scheduling problems besides cost also service-oriented objectives are of concern. In order to shed some light on their trade-off relationship, instead of using a weighted sum objective function, we introduce separate service-oriented objectives into the generalized consistent vehicle routing problem (GenConVRP) and into the home care routing and scheduling problem (HCRSP). In the multi-objective GenConVRP, in addition to routing costs, we optimize the maximum number of different drivers per customer (driver consistency) and the maximum arrival time difference on two different days in the planning horizon (arrival time consistency). In the bi-objective HCRSP, besides minimizing routing and overtime costs, we maximize the service level with respect to preferred visit times and nurses. Overtime costs in combination with interval preferences on preferred visit times results in a scheduling problem for each route that is a bi-objective problem in itself, which is a distinctive characteristic of the bi-objective HCRSP. For both problems we solve small instances to optimality using the epsilon-constraint scheme. To solve larger instances we devise algorithms combining large neighborhood search and multi-directional local search. We can show that a considerable trade-off between cost and client-oriented objectives exists. However, our results also reveal that, using the minimum cost solution as a basis, the considered visit time-oriented service levels may be improved drastically with only small additional costs. In the GenConVRP, visiting each customer by the same driver each time is significantly more expensive than allowing at least two drivers and, in several cases, arrival time consistency and driver consistency can be improved simultaneously.