The multi-shiftvehicleroutingproblemwithovertime

In thispaper,westudyanewvariantofthevehicleroutingproblem(VRP)withtimewindows,multi- shift, andovertime.Inthisproblem,alimitedfleetofvehiclesisusedrepeatedlytoservedemandovera planninghorizonofseveraldays.Thevehiclesusuallytakelongtripsandtherearesignificantdemands near shiftchanges.Theproblemisinspiredbyaroutingprobleminhealthcare,wherethevehicles continuouslyoperateinshifts,andovertimeisallowed.Westudywhetherthetradeoffbetween overtimeandotheroperationalcostssuchastravelcost,regulardriverusage,andcostofunmet demandscanleadtoamoreefficientsolution.Wedevelopashiftdependent(SD)heuristicthattakes overtimeintoaccountwhenconstructingroutes.WeshowthattheSDalgorithmhassignificantsavings in totalcostaswellasthenumberofvehiclesoverconstructingtheroutesindependentlyineachshift, in particularwhendemandsareclusteredornon-uniform.LowerboundsareobtainedbysolvingtheLP relaxationoftheMIPmodelwithspecializedcuts.ThesolutionoftheSDalgorithmonthetestproblems is within1.09–1.82timestheoptimalsolutiondependingonthetimewindowwidth,withthesmaller time windowsprovidingthetighterbounds.