An exact algorithm for the home health care routing and scheduling with electric vehicles and synergistic-transport mode
Abstract
Increasing environmental concerns and the advancement of battery technologies have attracted a growing focus on electric vehicles (EVs) for green travel and distribution. We consider the home health care routing and scheduling with electric vehicles and synergistic-transport mode, where the EVs are used to transport care-workers to serve patients. By synergistic-transport mode, we mean that a care-worker may choose to serve patients by other transport modes, referred to as by walking, when the EV is recharging at a recharging station, and then rendezvous with the EV either at the recharging station or at a patient node. The objective is to find the synthetic-routes, each of which is composed of the EV route and the walking routes of a care-worker, so as to minimize the sum of the dispatching cost, the transport cost by EV and walking, and the incompatibility cost of care-workers and patients. To solve the problem, we develop a tailored branch-and-price-and-cut algorithm based on a set-partitioning model, incorporating a specified bounded bidirectional labelling algorithm to solve the challenging pricing subproblems which involve the collaboration of two transport modes to find the synthetic-routes with negative reduced cost. To enhance the performance of the algorithm, we employ the subset-row inequalities to tighten the lower bound and apply two heuristics including variable neighborhood search and hierarchical column generation to solve the pricing subproblems quickly. Extensive computational studies show that our synergistic-transport mode can yield significant cost savings over the EV-only transport mode, and that the developed algorithm is able to solve large-scale instances efficiently within reasonable computational time.