Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics

Abstract : This paper addresses a periodic vehicle routing problem encountered in home health care (HHC) logistics. It extends the classical Periodic Vehicle Routing Problem with Time Windows (PVRPTW) to three types of demands of patients at home. Demands include transportation of drugs/medical devices between the \{HHC\} depot and patients׳ homes, delivery of special drugs from the hospital to patients, and delivery of blood samples from patients to the lab. Each patient requires a certain number of visits within a planning horizon and has a set of possible combinations of visit days. Daily routing should meet time window constraints associated with patients, the hospital and the lab. The problem consists in determining the visit days of each patient and vehicle routes for each day in order to minimize the maximal routing costs among all routes over the horizon. We propose a Tabu Search method combined with different local search schemes including both feasible and infeasible local searches. The proposed approaches are tested on a range of instances derived from existing Vehicle Routing Problem with Time Window (VRPTW) benchmarks and benchmarks on special cases of our problem. Numerical results show that local search scheme starting with an infeasible local search with a small probability followed by a feasible local search with high probability is an interesting hybridization. Experiments with field data from a \{HHC\} company show that the proposed approach reduces the total cost and better balances the workloads of vehicles.
Document type :
Journal articles
Complete list of metadatas

Cited literature [67 references]  Display  Hide  Download

https://hal-emse.ccsd.cnrs.fr/emse-01109346
Contributor : Amélie Chatagnon <>
Submitted on : Monday, February 22, 2016 - 5:25:22 PM
Last modification on : Friday, March 15, 2019 - 1:14:45 AM
Long-term archiving on : Monday, May 23, 2016 - 3:04:23 PM

File

2014 Hybridization of Tabu - L...
Files produced by the author(s)

Identifiers

Citation

Ran Liu, Xiaolan Xie, Thierry Garaix. Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics. Alpha Omegan, Elsevier Masson, 2014, 47, pp.17-32. ⟨10.1016/j.omega.2014.03.003⟩. ⟨emse-01109346⟩

Share

Metrics

Record views

390

Files downloads

419