reasonssuperpi

IteratedlocalsearchalgorithmforsolvingtheorienteeringproblemwithsofttimewindowsBrahimAghezzafandHassanElFahim*BackgroundInorienteeringproblem(OP)asetofpotentialcustomersisgiven;theserviceforthesecustomersisoptionalduringthecurrentplanningtimehorizonsincethetravelcostoftherouteislimited.
Thetravelcostisoftenexpressedasthetraveltimeorthetraveldis-tance.
Thus,apositivevaluecalledprofitisassociatedwitheverycustomermakingitsvisitmoreorlessattractive.
Thenameofthisroutingproblemoriginatesfromagameinwhichcompetitorshavetovisitasetofcontrolpointsinagivenarea.
Ifthecontrolpointisvisited,thecompetitorgetsaprofit.
Thewinnerofthegameisthecompetitorwhocollectsmaximumprofitsandgetstotheendpointwithinaprescribedamountoftime.
Asaroutingproblem,theOPconsistsinfindingtheroutevisitingasubsetofcus-tomersthatmaximizesthetotalcollectedprofitwhilesatisfyingthemaximumdurationconstraint.
TheOPisalsoknownintheliteratureastheSelectiveTravelingSalesmanProblem(ThomadsenandStidsen2003),theMaximumCollectionProblem(ButtandCavalier1994)andtheBankRobberProblem(Awerbuchetal.
1998).
FewvehicleroutingproblemshavesuchapplicabilityasOP.
Thisproblemarisesinavarietyofapplicationsincludingdesignoftouristtripstomaximizethevalueofthevis-itedattractions(VansteenwegenandOudheusden2007),recruitingofathletesfromhighschoolsforacollegeteam(ButtandCavalier1994),deliveryofhomeheatingfuelwhereAbstractInthispaperwestudytheorienteeringproblemwithtimewindows(OPTW)andtheimpactofrelaxingthetimewindowsontheprofitcollectedbythevehicle.
Thewayofrelaxingtimewindowsadoptedintheorienteeringproblemwithsofttimewindows(OPSTW)thatwestudyinthisresearchisalateservicerelaxationthatallowslinearlypenalizedlateservicestocustomers.
Wesolvethisproblemheuristicallybyconsider-ingahybriditeratedlocalsearch.
TheresultsofthecomputationalstudyshowthattheproposedapproachisabletoachievepromisingsolutionsontheOPTWtestinstancesavailableintheliterature,onenewbestsolutionisfound.
OnthenewlygeneratedtestinstancesoftheOPSTW,theresultsshowthattheprofitcollectedbytheOPSTWisbet-terthantheprofitcollectedbytheOPTW.
Keywords:Combinatorialoptimization,Orienteeringproblem,Softtimewindow,Iteratedlocalsearch,VariableneighborhoodsearchOpenAccess2016TheAuthor(s).
ThisarticleisdistributedunderthetermsoftheCreativeCommonsAttribution4.
0InternationalLicense(http://creativecommons.
org/licenses/by/4.
0/),whichpermitsunrestricteduse,distribution,andreproductioninanymedium,providedyougiveappropriatecredittotheoriginalauthor(s)andthesource,providealinktotheCreativeCommonslicense,andindicateifchangesweremade.
RESEARCHAghezzafandFahimSpringerPlus(2016)5:1781DOI10.
1186/s40064-016-3440-6*Correspondence:elfahimhassan@gmail.
comLaboratoireInformatiqueetAideàlaDécision(LIAD),DépartementdeMathématiquesetInformatique,FacultédesSciencesAnChock,UniversitéHassanIIdeCasablanca,Km8Routed'ElJadida,5366Maarif,20100Casablanca,MoroccoPage2of36AghezzafandFahimSpringerPlus(2016)5:1781theurgencyofacustomerforfuelistreatedasaprofit(Goldenetal.
1984),routingofoiltankerstoserveshipsatdifferentlocations(Goldenetal.
1987)andreverselogisticsproblemofafirmthataimstocollectusedproductsfromitsdealers(Arasetal.
2011).
TheOPisawell-studiedcombinatorialoptimizationproblemthatwasfirstpresentedandheuristicallysolvedbyTsiligirides(1984).
SeveralheuristicsandmetaheuristicswereproposedforthesolutionoftheOP[thereaderisreferredforexampletothepapersbyTasgetiren(2001),RameshandBrown(1991)andGendreauetal.
(1998)].
InthetimewindowsversionoftheOPcalledtheorienteeringproblemwithtimewin-dows(OPTW),customershavehardtimewindowsandservicetimes.
Inhardtimewin-dows,arrivingatcustomerlaterthanlatesttimeofitstimewindowisstrictlyforbidden.
Awaitingisincurredifthevehiclereachestoacustomerbeforeitsearliesttimewindow.
InOPTW,theobjectiveisdesigningtheroutethatmaximizesthetotalcollectedprofitwhilesatisfyingthetimelimitdurationandthehardtimewindowsconstraints.
InrecentyearstherehasbeenconsiderableinterestfortheOPTWwhichhasledtoasignificantbodyofliterature.
TheauthorsinRighiniandSalani(2009)proposedabidi-rectionaldynamicprogrammingalgorithmforsolvingtheOPTWtooptimality.
Theyuseatechniquenameddecrementalstatespacerelaxationinwhichthedynamicpro-grammingalgorithmtakesadvantageofastatespacerelaxation.
TheauthorsinDuqueetal.
(2015)proposedanexactalgorithmbasedonpulseframeworkforsolvingtheOPTWtooptimality.
Moststudieshavefocusedondesigningheuristicalgorithms,sev-eralheuristicsandmetaheuristicswerethenproposedforthesolutionoftheOPTW[thereaderisreferredforexampletothepapersbyVansteenwegenetal.
(2009),LinandYu(2012),Labadieetal.
(2011,2012),MontemanniandGambardella(2009),Tunchan(2014),Gunawanetal.
(2015)andLahyanietal.
(2016)].
ForarecentsurveyonOPandOPTWthereaderisreferredtothepaperbyGunawanetal.
(2016).
Problemrelatedtotheproblemstudiedinthisresearchisthevehicleroutingproblemwithsofttimewindows(VRPSTW).
Inmanyreal-lifeproblems,someorallcustomers'timewindowsarenotsostrictthatcanbeviolatedwithappropriatepenalties.
Suchkindoftimeconstraintiscalledsofttimewindow.
InVRPSTW,vehiclesareallowedtoservecustomersbeforetheearliestand/orafterthelatesttimewindowsbounds.
Thistypeoftimewindowsisusefulforthedispatcherwhen:Thenumberofroutesneededforhardtimewindowsexceedsthenumberofavail-ablevehicles.
Astudyofcost-servicetradeoffsisrequired.
Thedispatcherhasqualitativeinformationregardingtherelativeimportanceofhardtimewindowsacrosscustomers.
Besides,relaxingtimewindowscanresultinlowertotalcostswithouthurtingcustom-ers'satisfactionsignificantly.
Intheliterature,therearedifferentwaysofrelaxingtimewindowswhichleadtodifferentvariantsofVRPSTW.
Ifavehiclearrivesbeforetheearliestboundofthetimewindow,itwaitsasinhardtimewindowscase.
However,lateserviceisallowedifanappropriatepenaltyispaid.
TheauthorsinTaillardetal.
(1997)proposedatabusearchheuristicforthisvariant.
Page3of36AghezzafandFahimSpringerPlus(2016)5:1781Bothearlyandlateservicesareallowedbypayingappropriatepenalties.
TheauthorsinKoskosidisandSolomon(1992)proposedanoptimization-basedheuristicforthisvariant.
Bothearlyandlateservicesareallowedasinthesecondvariant.
However,themaximumallowableviolationofthetimewindowsandthemaximumwaitingtimeallowedarelimited.
ThisisthevariantstudiedbyChiangandRussell(2004)andBal-akrishnan(1993).
TheauthorsinBalakrishnan(1993)describedthreeheuristicsforsolvingthisvariant.
WhiletheauthorsinChiangandRussell(2004)proposedatabusearchheuristictodealwiththisvariant.
Formoredetailabouttheserelaxationschemesandthealgorithmsproposedinthelit-eraturetosolvingthem,thereaderisreferredtothepaperbyVidaletal.
(2015).
ContributionsWeobservedwhensolvingorienteeringproblemswithtimewindowsasinAghezzafandFahim(2015)thatthegapbetweenthetotaltraveltimeofarouteandthetraveltimelimitissignificantespeciallyoninstanceswithlongschedulinghorizon.
Thus,wehavedecidedtomanagethisgapbyallowingrelaxationoftimewindowsinordertoimprovetheprofitcollectedbythevehicle.
Furthermore,therearemanypracticalreasonsforallowingviolationoftimewindows:Manyapplicationsdonotrequirehardtimewindows.
Inmanycasestraveltimescannotbeaccuratelyknown.
Customersmaybeunwillingtosetprecisetimewindowsinadvanceandsimplypre-fertheflexibilitytoaltertheirdeliveryrequests.
Thecontributionofthispaperistwofold:Weintroduceanddefineanewroutingdenotedtheorienteeringproblemwithsofttimewindows(OPSTW).
Tothebestofourknowledge,thisisthefirststudydeal-ingwithorienteeringproblemwithsofttimewindows.
Inthisroutingproblem,lateserviceisallowedifanappropriatepenaltyispaid.
Inthisrelaxationscheme,weareplacingrestrictionsonboththepenaltypayableandthewaitingtime.
WethinkthatOPSTWsolutionscanresultinroutesvisitingasignificantnumberofpotentialcus-tomerswithouthurtingcustomers'satisfactionsignificantly.
Furthermore,softtimewindowscanprovideaworkableplanofactionfordecisionmakerswhenhardtimewindowsarenotrequiredorwhenitisnotpossibletovisitallcustomersduringthecurrentplanningtimehorizonwhichisthecasefortheOPTW.
Wedevelopahybridalgorithmthatcombinesaniteratedlocalsearchwithavariableneighborhoodsearchforthisspecificproblem.
WealsoapplyittostandardinstancesandcompareitsperformancetothatofotheralgorithmsproposedintheliteraturefortheOPTW.
Therestofthispaperincludesfouradditionalsections.
"Mathematicalmodel"sectiondefinesthemathematicalnotationandformulationofOPSTW.
"Solutionalgorithm"sec-tiondescribestheproposedhybridalgorithm.
"Computationalresults"sectionpresentsPage4of36AghezzafandFahimSpringerPlus(2016)5:1781thecomputationalresultsandcomparesouralgorithmagainstpublishedresultsbothwithregardtosolutionqualityandcomputationaltime.
Thelastsectionisdevotedtotheconclusions.
MathematicalmodelTheOPTWstudiedinthispapercanbedescribedasfollows:letG=(V,E)beacom-pletegraph,whereV={0,1,n}isavertexsetandE={(i,j)∈V2i=j}isanarcset.
Vertex0denotesadepotatwhichthevehiclestartsandendsitstour.
Thesetofverti-cesC={1,n}specifythelocationofasetofncustomers.
Eachvertexi∈Vhasanassociatedprofitpi(p0=0),aservicetimeSi(S0=0)andatimewindow[ei,li]whichisassumedtobehard.
Eacharc(i,j)∈Ehasanassociatedcosttijwhichrepresentsthetimerequiredtotravelfromvertexitovertexj.
ThecosttijisdefinedastheEuclideandistancebetweenthepointscorrespondingtoiandj.
Thearrivaltimetoacustomeriisdenotedai;thebeginningofservicetimeisdenotedbi.
TheobjectiveistodesignarouteRthatmaximizesthetotalcollectedprofitsubjecttothefollowing:TherouteRcannotstartbeforee0andcannotendafterl0.
Theservicetoacustomericannotstartbeforeeiandifthevehiclearrivestooearlyitcanwaitforacertainperiodoftimewi=max(eiai,0)andservesthatcustomer.
Everycustomerisvisitedatmostonce.
ThetotaltraveltimeofRislimitedbyatimelimitTmax.
Inordertoformulatethemodelwedefinethefollowingdecisionvariables:xijbinaryvariableequalto1ifthevehicletravelsdirectlyfromvertexitovertexj,and0otherwise.
yibinaryvariableequalto1ifvertexiisvisited,and0otherwise.
bibeginningofservicetimeatcustomeri.
Misalargevalue.
TheOPTWcanbeformulatedasthefollowingmixedintegerlinearprogrammingmodel:(1)maxf=i∈Cpiyi(2)subjectto:j∈Cx0j=i∈Cxi0=1(3)i∈Vxil=j∈Vxlj≤1l∈C(4)bi+Si+tijbj≤M(1xij)i,j∈V(5)i∈VSiyi+j∈Vtijxij≤TmaxPage5of36AghezzafandFahimSpringerPlus(2016)5:1781Theobjectivefunction(1)maximizesthetotalcollectedprofit.
Constraint(2)guaranteesthattheroutestartsandendsatvertex0(depot).
Constraints(3)and(4)determinetheconnectivityandthetimelineoftheroute.
Constraint(5)ensuresthemaximumtimedurationconstraintoftheroute.
Constraints(6)restrictthestartofthevisittothetimewindows.
Constraints(7)and(8)arevariablesdefinition.
InOPSTW,thetimewindowofeverycustomeri∈Ccanbeenlargedtoanoutertimewindow[ei,li+Pmax]=[ei,li],wherePmaxisanupperboundonthemaximumallow-abletimewindowviolation.
AnappropriatepenaltyPpenaltyiisthenpaidiftheservicestartslatethatisai∈]li,li].
Thepenaltyfunctioncanbedefinedasfollows:OnecanexpresstheOPSTWobjectivefunctionasacombinationbetweenthetotalcol-lectedprofit(theclassicobjectiveforOPTW)andthetotalpenaltyfortimewindowsviolations.
Inourformulation,wedonotexpressitthatwaysincethiswillchangethenatureofthefacedproblemandtheaimofthiswork.
InourOPSTWformulation,thetotalpenaltyandthetotalwaitingtimeareexpressedastravelcostsandaddedtothetotaltraveltimeoftheroute.
Then,constraint(5)ofthepreviousmodelchangesasfollows:Sinceinourformulationwetakeintoaccountthefactthatwi≤Wmaxforeachroutedcustomeri,thefollowingconstraintisaddedtothemodel.
Regardingthetimewindowsconstraintstheychangeasfollows:Inthenextsubsection,wewilldescribetheapproachthatweproposetodealwiththeOPSTW.
(6)ei≤bi≤lii∈V(7)xij,yi∈{0,1}i,j∈V(8)bi∈R+∩[e0,l0]i∈V(9)Ppenaltyi=0ifeiWmax≤ai≤liailiiflisuperpi.
net/).
InTable2,theSuperpicolumnreportsthenumberofsecondsittakeseachprocessortocomputethefirstonemilliondigitsofπ.
TheprocessorusedforIterLSalgorithmisapproximatelytwotimesfasterthanthatusedforGRASP-ELSandGVNSalgorithms;theprocessorusedforVANalgorithmisslowerthanthatusedforGRASP-ELSandGVNSalgorithms.
WhiletheprocessorusedforACSandEACSalgorithmsiscompara-bletothatusedforGRASP-ELSandGVNSalgorithms.
Thisstatementisbasedonthecomparisonofvariouscomputersystemssolvingstandardlinearequationproblemspre-sentedinDongarra(2014).
Theperformanceisevaluatedonabenchmarkproblemofadensesystemoflinearequationsgivenbyamatrixoforder100and1000.
ThevaluesfortheprocessorusedforGRASP-ELSandGVNSalgorithmsare1571and3650Mflop/srespectively;thevaluesfortheprocessorusedforACSandEACSalgorithmsare1470and3654Mflop/srespectively.
ThevaluesfortheprocessorusedforIterLSalgorithmare2426and7519Mflop/srespectivelywhilethevaluesfortheprocessorusedforVANalgorithmare1317and2444Mflop/srespectively.
ThevaluesfortheprocessorusedforVNSwhichisanIntelPentium4with2.
4GHzarenotavailable.
However,thevaluesforanIntelPentium4with2.
5GHzareavailable,thisprocessorhasachieved1190and2355Mflop/srespectively.
Thus,weassumethattheprocessorusedforVNSalgorithmisslowerthanthatusedforVANalgorithm.
ThevaluesfortheprocessorusedforGATable2Estimateofsingle-threadperformanceAlgorithmExperimentalenvironmentSuperPiEstimateofsingle-threadperformanceACSDualAMDOpteron2502.
4GHzCPU,4GBRAMUnknown0.
22EACSDualAMDOpteron2502.
4GHzCPU,4GBRAMUnknown0.
22IterLSIntelcore22.
5GHzCPU,3.
45GBRAM18.
60.
53VNS2.
4GHzCPU,4GBRAMUnknown<0.
22GRASP-ELSIntelPentium4processor,3.
00GHz,1GBRAM44.
30.
22SSAIntelCore2CPU,2.
5GHz18.
60.
53FSAIntelCore2CPU,2.
5GHz18.
60.
53GVNSIntelPentium(R)IV,3GHzCPU44.
30.
22I3CHIntelXeonE5430CPUclockedat2.
66GHz,8GBRAM14.
70.
67HILSIntel(R)Pentium(R)CPUB950,2.
1GHz,4GBRAM230.
43ABCAMDAthlonX22503.
00GHz32.
10.
31ILSIntelCorei7-4770with3.
4GHz,16GBRAM9.
81GAIntelCorei7,1.
73GHzCPU(turboboostto2.
93GHz)Unknown≤0.
70DABCIntelCore2Quadprocessorwith2.
66GHzCPUUnknown≤0.
67VANIntelPentium4with2.
8GHz,1GBRAMUnknown<0.
22Page29of36AghezzafandFahimSpringerPlus(2016)5:1781algorithmarenotavailable.
AsonlylimitedinformationwasavailableontheprocessorusedbyGA,wecannotestimateitsspeedbyconsideringonlytheclock-rate.
Areviewofallprocessorsi7with2.
93GHzshowsthattheSuperpirangesfrom13.
8to11.
7s.
WeassumethattheprocessorusedforDABCiscomparabletothatusedforI3CHalgo-rithm.
Weestimatethesingle-threadperformanceofeachprocessorbysupposingtheperformanceofthemachineofGunawanetal.
(2015)tobe1.
Table3summarizestheresultsobtainedbythealgorithms.
Itcomparestheaver-ageperformanceofHILSwiththatofthestat-of-the-artalgorithms.
ColumnGap(%)reportstheaveragepercentualgapwiththebestknownprofit.
ColumnCPU(s)reportstheaveragecomputationaltimeinseconds.
Thecomputationaltimesofthealgorithmsareadjustedaccordingtocomputers'speedaspresentedinTable2.
TheauthorsinMon-temannietal.
(2011)didnotreportdetailedresultsfortheirEACSalgorithm,theyhavejustreportedaveragegapswiththeformerbestknownsolutions.
However,theauthorsinGunawanetal.
(2015)haverecentlyreportedtheaveragegapsforthebestalgorithmamongACSandEACScalledACS*withthelatestbestknownsolutions.
Thus,columnACS*ofTable3presentstheaverageresult,overfiveruns,ofACS*algorithm.
WecanseefromTables1and3thatonSolomoninstanceswith100customers,HILSalgorithmperforms,onaverage,betterthanGVNSandDABConClass1(C100,R100andRC100)bothwithregardtosolutionqualityandcomputationaltime.
OnC100andR100testinstances,HILSalgorithmperforms,onaverage,betterthanFSA,GAandIterLSusingapproximatelythesamecomputationaleffort.
OntheseinstancesofClass1,ILS,SSAandGRASP-ELSandI3CHare,onaverage,betterthanHILSatthecostofextracomputationaltime.
OnthetestinstancesofClass2(C200,R200andRC200),HILSalgorithmperforms,onaverage,betterthanGAusingmorecomputationaltime.
OnC200testinstances,HILSperforms,onaverage,betterthanGVNSbothwithregardtosolutionqualityandcomputationaltime.
OntheseinstancesofClass2,mostofstate-of-the-artalgorithmsoutperformHILSalgorithmusingmorecomputationaleffort.
OnthesetestinstancesofSolomonwith100customers,HILSachievedtheoptimalsolution19times.
OnthetestinstancesofCordeau,HILSalgorithmisnotascompetitiveasstate-of-the-artalgorithmsonPR01-10testinstances;HILSalgorithmachievedtheworstaver-agegapwhichisequalto6.
8%.
OnPR11-20testinstancesofCordeau,HILSalgorithmperforms,onaverage,betterthanACS*bothwithregardtosolutionqualityandcompu-tationaltimeandbetterthanFSAusingmorecomputationaleffort.
However,therestofstate-of-the-artalgorithmsperform,onaverage,betterthanHILSonthesetestinstancesofCordeau.
HILSalgorithmisabletoachieve1newbestsolutiononPR17testinstance.
Ontestinstanceswith50customers,HILSalgorithmisascompetitiveasVANalgo-rithmbothwithregardtosolutionqualityandcomputationaltime.
VNSalgorithmper-forms,onaverage,betterthanHILSandVANalgorithmsattheexpenseofareasonableamountofcomputationaltime.
Ontheseinstances,HILSisabletoachievetheoptimalsolutionon19instancesover29.
ComputationalresultsonOPSTWinstancesInthissectionwecomputationallytesttheincreaseoftheprofitduetosofttimewindows.
Page30of36AghezzafandFahimSpringerPlus(2016)5:1781Table3OverallcomparisononOPTWtestinstancesSetI3CHABCVNSILSACSGVNSGap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)C100-1000.
016.
90.
10.
80.
1<21.
60.
01.
00.
01.
41.
336.
6R100-1000.
619.
21.
01.
10.
1<19.
60.
01.
80.
284.
32.
86.
5RC100-1001.
917.
20.
12.
40.
0<14.
40.
01.
00.
031.
53.
72.
2PR01-101.
173.
01.
524.
31.
1<163.
70.
750.
41.
2357.
91.
62.
7C200-1000.
456.
50.
53.
40.
2<123.
20.
190.
00.
675.
41.
142.
3R200-1001.
4118.
12.
18.
21.
4<234.
51.
3162.
13.
5342.
53.
87.
4RC200-1002.
879.
91.
87.
51.
5<191.
31.
1120.
52.
2191.
34.
13.
5PR11-204.
387.
23.
632.
43.
4<230.
12.
197.
911.
9195.
34.
35.
3SetGRASP-ELSSSAIterLSFSADABCHILSGap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)Gap(%)CPU(s)C100-1000.
05.
00.
011.
21.
20.
20.
90.
31.
7≤11.
60.
30.
2R100-1000.
20.
80.
112.
32.
00.
23.
20.
12.
6≤17.
00.
60.
3RC100-1000.
40.
40.
011.
83.
10.
27.
40.
15.
5≤19.
23.
50.
1PR01-101.
51.
11.
059.
54.
71.
05.
31.
0––6.
81.
2C200-1000.
67.
10.
119.
92.
30.
91.
10.
90.
6≤72.
20.
82.
6R200-1002.
02.
51.
724.
33.
30.
93.
90.
91.
0≤90.
95.
18.
3RC200-1002.
31.
81.
126.
73.
60.
85.
50.
81.
8≤72.
04.
93.
9PR11-203.
41.
73.
786.
19.
61.
110.
21.
1––9.
42.
7Page31of36AghezzafandFahimSpringerPlus(2016)5:1781Table3continuedSetGAACS*Gap(%)CPU(s)Gap(%)CPU(s)C100-1001.
1≤0.
20.
01.
4R100-1001.
8≤0.
20.
284.
8RC100-1002.
4≤0.
20.
031.
7PR01-10––1.
2359.
8C200-1002.
5≤0.
70.
675.
8R200-1007.
1≤1.
43.
2344.
4RC200-1007.
6≤1.
12.
0341.
7PR11-20––11.
9196.
4Page32of36AghezzafandFahimSpringerPlus(2016)5:1781Table4ResultsontheOPSTWtestinstancesInstance(Pmax,Wmax)HILSBestWorstAverageCPU(s)NR%HTWRoutedcustomersPR01(1.
0,5.
0)3233233230.
41994.
79,47,24,38,30,2,37,10,45,32,21,16,36,43,31,35,34,22,7(1.
5,5.
0)3223223220.
41984.
29,47,12,38,24,32,37,10,45,16,21,23,36,43,31,35,34,22,7(2.
0,5.
0)3293293290.
42085.
09,47,24,12,38,37,10,45,11,32,23,21,16,36,43,31,35,34,22,7(2.
5,5.
0)3323323320.
42180.
99,47,24,12,38,37,10,45,11,32,23,21,16,36,43,31,44,35,34,22,7(3.
0,5.
0)3333333330.
42180.
99,47,12,38,24,32,37,10,45,41,16,21,23,36,43,31,44,35,34,22,7(3.
5,5.
0)3373373370.
42176.
29,47,12,38,24,32,37,10,45,11,41,16,21,23,36,43,31,35,34,22,7(4.
0,5.
0)3383383380.
22180.
99,47,24,38,12,32,37,10,45,41,1,16,21,26,23,43,31,35,34,22,7(4.
5,5.
0)3463463460.
42378.
39,47,24,38,12,32,37,10,45,41,28,1,16,21,26,36,43,31,44,35,34,22,7(5.
0,5.
0)3383383380.
420759,47,12,38,24,32,37,10,45,41,16,21,36,43,31,42,22,34,35,7(1.
0,5.
5)3173173170.
42090.
09,47,24,38,12,32,37,10,45,16,21,26,36,43,31,44,35,34,22,7(1.
5,5.
5)3223223220.
41984.
29,47,12,38,24,32,37,10,45,16,21,23,36,43,31,35,34,22,7(2.
0,5.
5)3293293290.
42085.
09,47,24,12,38,37,10,45,11,32,23,21,16,36,43,31,35,34,22,7(2.
5,5.
5)3323323320.
42180.
99,47,24,12,38,37,10,45,11,32,23,21,16,36,43,31,44,35,34,22,7(3.
0,5.
5)3333333330.
42180.
99,47,12,38,24,32,37,10,45,41,16,21,23,36,43,31,44,35,34,22,7(3.
5,5.
5)3373373370.
42176.
29,47,12,38,24,32,37,10,45,11,41,16,21,23,36,43,31,35,34,22,7(4.
0,5.
5)3373373370.
42281.
89,47,24,38,12,32,37,10,45,41,1,16,21,26,36,43,31,44,35,34,22,7(4.
5,5.
5)3463463460.
42378.
39,47,24,38,12,32,37,10,45,41,28,1,16,21,26,36,43,31,44,35,34,22,7(5.
0,5.
5)3383383380.
42075.
09,47,12,38,24,32,37,10,45,41,16,21,36,43,31,42,22,34,35,7(1.
0,6.
0)3233233230.
41994.
79,47,24,38,30,2,37,10,45,32,21,16,36,43,31,35,34,22,7(1.
5,6.
0)3223223220.
41984.
29,47,24,38,12,32,37,10,45,16,21,23,36,43,31,35,34,22,7(2.
0,6.
0)3293293290.
42085.
09,47,24,12,38,37,10,45,11,32,23,21,16,36,43,31,35,34,22,7(2.
5,6.
0)3323323320.
42180.
99,47,24,12,38,37,10,45,11,32,23,21,16,36,43,31,44,35,34,22,7(3.
0,6.
0)3333333330.
42180.
99,47,12,38,24,32,37,10,45,41,16,21,23,36,43,31,44,35,34,22,7(3.
5,6.
0)3373373370.
42176.
29,47,12,38,24,32,37,10,45,11,41,16,21,23,36,43,31,35,34,22,7(4.
0,6.
0)3373373370.
42281.
89,47,24,38,12,32,37,10,45,41,1,16,21,26,36,43,31,44,35,34,22,7Page33of36AghezzafandFahimSpringerPlus(2016)5:1781Table4continuedInstance(Pmax,Wmax)HILSBestWorstAverageCPU(s)NR%HTWRoutedcustomers(4.
5,6.
0)3463463460.
42378.
39,47,24,38,12,32,37,10,45,41,28,1,16,21,26,36,43,31,44,35,34,22,7(5.
0,6.
0)3383383380.
420759,47,12,38,24,32,37,10,45,41,16,21,36,43,31,42,22,34,35,7(1.
0,6.
5)3303303300.
42090.
09,47,24,38,30,2,32,37,10,45,11,36,21,16,43,31,35,34,22,7(1.
5,6.
5)3333333330.
42185.
79,47,24,38,30,2,32,37,10,45,11,36,21,16,43,31,44,35,34,22,7(2.
0,6.
5)3363363360.
42176.
29,47,24,12,38,30,2,32,37,10,45,11,21,16,36,43,31,35,34,22,7(2.
5,6.
5)3383383380.
42180.
99,47,24,38,30,2,32,37,10,45,11,41,36,21,16,43,31,35,34,22,7(3.
0,6.
5)3413413410.
52281.
89,47,24,38,30,2,32,37,10,45,11,41,36,21,16,43,31,44,35,34,22,7(3.
5,6.
5)3423423420.
42180.
99,47,24,38,30,2,32,37,10,45,11,36,21,16,1,43,31,35,34,22,7(4.
0,6.
5)3423423420.
42180.
99,47,24,38,30,2,32,37,10,45,11,36,21,16,1,43,31,35,34,22,7(4.
5,6.
5)3313313310.
51968.
49,47,24,38,12,32,37,10,45,21,29,8,16,43,44,35,34,22,7(5.
0,6.
5)3483483480.
52166.
79,47,24,12,38,30,2,32,37,45,11,10,42,21,16,43,31,35,34,22,7(1.
0,7.
0)3303303300.
42095.
09,24,47,38,30,2,32,37,10,45,11,21,16,36,43,31,35,34,22,7(1.
5,7.
0)3333333330.
42195.
29,24,47,38,30,2,32,37,10,45,11,21,16,36,43,31,44,35,34,22,7(2.
0,7.
0)3373373370.
42185.
79,24,47,12,38,30,2,32,37,10,45,41,21,16,36,43,31,35,34,22,7(2.
5,7.
0)3363363360.
42277.
39,24,47,12,38,30,2,32,11,45,10,41,21,16,36,43,31,44,35,34,22,7(3.
0,7.
0)3443443440.
42281.
19,24,47,12,38,30,2,32,37,10,11,45,41,21,16,36,43,31,35,34,22,7(3.
5,7.
0)3373373370.
22176.
29,24,12,38,47,32,37,10,45,11,2,23,21,16,36,43,31,35,34,22,7(4.
0,7.
0)3293293290.
42070.
024,47,30,9,10,37,45,11,32,2,23,21,16,36,43,31,35,34,22,7(4.
5,7.
0)3303303300.
41978.
99,24,47,12,38,32,37,45,10,21,16,36,43,31,42,22,35,34,7(5.
0,7.
0)3483483480.
42171.
49,24,47,12,38,30,2,32,37,11,45,10,42,21,16,43,31,35,34,22,7Page34of36AghezzafandFahimSpringerPlus(2016)5:1781Table4presentstheresultsobtainedbyHILSalgorithmonOPSTWtestinstances.
Columnone(Instance)presentstheinstanceoverwhichthealgorithmistested.
Columntwocorrespondstothemaximumallowabletimewindowviolationandthemaximumallowablewaitingtimeatanycustomer.
Columnsthreetosixpresentthebest,worstandaverageprofit,overfiveruns,ofHILSalgorithmandtheaveragecomputationaltime.
ColumnsNRand%HTWpresentthenumberofroutedcustomersontheaveragesolutionandthepercentageofnon-violatedtimewindowsonthissolutionrespectively.
Thelastcolumnpresentsthesequenceinwhichthecustomersareroutedintheaveragesolution.
Theresultsshow,asexpected,thatinallcasesitispossibletoincreasethecollectedprofitbyallowingcontrolledviolationsoftimewindows.
Allowingforexamplethemax-imumallowableviolationoftimewindowto1%ofthemaximumtimedurationandthemaximumallowablewaitingtimeatanycustomerto7%ofthemaximumtimeduration,resultsinsolutionwithaprofitof330and95%ofnon-violatedtimewindowswhiletheprofitreportedforhardtimewindowsis308.
Ontheotherhand,settingforexam-plePmaxto4.
5%andWmaxto5%,resultsin23routedcustomerswhilethenumberofroutedcustomersreportedforhardtimewindowsis21.
ConclusionsInthispaperwehaveintroducedtheorienteeringproblemwithsofttimewindows(OPSTW).
Thisroutingproblemcanserveasamodelformanypracticalapplicationsforwhichtraveltimescannotbeaccuratelyknownorwhenhardtimewindowsarenotrequired.
ComputationalresultsonOPSTWshowthatourhybridalgorithmisabletoachievesolutionsthatincreasethetotalcollectedprofitwithouthurtingcustomers'sat-isfactionsignificantly.
OnOPTWtestinstancesourhybridalgorithmisabletoachievepromisingsolutions.
Inourtestexperiments,instanceswithtighttimewindowsaresolvedbetterthanthatwithbroadertimewindows.
A2-Optor3-Optproceduremayreducethisgapbydecreasingthetimedurationoftherouteandinsertingotherpossibleunroutedcustomers.
Sincethechosenacceptancecriterionhasacriticalinfluenceonthebalancebetweenintensificationanddiversificationofthesearch,apossibleimprove-mentofthealgorithmcouldinvolvealsoconsideringworstsolutionsduringthesearch.
Onecouldworkwithasimulatedannealingacceptancecriterion.
Authors'contributionsAllauthorscontributedequallyandsignificantlytothiswork.
Allauthorsdraftedthemanuscript.
Bothauthorsreadandapprovedthefinalmanuscript.
AcknowledgementsWeacknowledgethecontributionoftworeviewersthathavehelpedustoimproveapreviousversionofthispaper.
CompetinginterestsTheauthorsdeclarethattheyhavenocompetinginterests.
Received:24February2016Accepted:29September2016ReferencesAghezzafB,FahimHE(2015)Solvingthecapacitatedteamorienteeringproblemwithtimewindowsthroughvariableneighborhoodsearch.
IntRevComputSoftwIRECOS10(11):1134–1142Page35of36AghezzafandFahimSpringerPlus(2016)5:1781ArasN,AskenD,TekinMT(2011)Selectivemulti-depotvehicleroutingproblemwithpricing.
TranspResPartC19:866–884AwerbuchB,AzarY,BlumA,VempalaS(1998)Newapproximationguaranteesforminimum-weightk-treesandprize-collectionsalesmen.
SIAMJComput28:254–262BalakrishnanN(1993)Simpleheuristicforthevehicleroutingproblemwithsofttimewindows.
JOperResSoc44:279–287ButtSE,CavalierTM(1994)AHeuristicforthemultipletourmaximumcollectionproblem.
ComputOperRes21(1):101–111ChiangWC,RussellRA(2004)Ametaheuristicforthevehicleroutingproblemwithsofttimewindows.
JOperResSoc55:1298–1310CordeauJF,GendreauM,LaporteG(1997)Atabusearchheuristicforperiodicandmulti-depotvehicleroutingproblems.
Networks30:105–119DongarraJJ(2014)Performanceofvariouscomputersusingstandardlinearequationssoftware.
ElectricalEngineeringandComputerScienceDepartmentUniversityofTennessee,Knoxville(2014)DuqueD,LozanoL,MedagliaAL(2015)Solvingtheorienteeringproblemwithtimewindowsviathepulseframework.
ComputOperRes54:168–176GendreauM,LaporteG,SemetF(1998)Atabusearchheuristicfortheundirectedselectivetravellingsalesmanproblem.
EurJOperRes106:539–545GoldenBL,AssadA,DahlR(1984)Analysisofalarge-scalevehicleroutingproblemwithaninventorycomponent.
LargeScaleSyst7:181–190GoldenBL,LevyL,VohraR(1987)Theorienteeringproblem.
NavResLogist34(3):307–318GunawanA,LauHC,LuK(2015)Aniteratedlocalsearchalgorithmforsolvingtheorienteeringproblemwithtimewindows.
In:Evolutionarycomputationincombinatorialoptimization—15thEuropeanconference,EvoCOP2015,Copenhagen,Denmark,April8–10,2015,Proceedings,pp61–73GunawanA,LauHC,VansteenwegenP(2016)Orienteeringproblem:asurveyofrecentvariants,solutionapproachesandapplications.
EurJOperRes225(2):315–332HuQ,LimA(2014)Aniterativethree-componentheuristicfortheteamorienteeringproblemwithtimewindows.
EurJOperRes232(2):276–286KarabulutK,TasgetirenMF(2013)Adiscreteartificialbeecolonyalgorithmfortheteamorienteeringproblemwithtimewindows.
In:IEEEsymposiumoncomputationalintelligenceinproductionandlogisticssystems,CIPLS2013,Singapore,April16–19,2013,pp99–106(2013)Karbowska-ChilinskaJ,ZabielskiP(2014)Geneticalgorithmwithpathrelinkingfortheorienteeringproblemwithtimewindows.
FundamInf135(4):419–431KoskosidisYA,SolomonWBPMM(1992)Anoptimization-basedheuristicforvehicleroutingandschedulingwithsofttimewindowsconstraints.
TranspSci26:69–85LabadieN,MansiniR,MelechovskJ,CalvoRW(2011)Hybridizedevolutionarylocalsearchfortheteamorienteeringproblemwithtimewindows.
JHeuristics17:729–753LabadieN,MansiniR,MelechovskJ,CalvoRW(2012)Theteamorienteeringproblemwithtimewindows:anLP-basedgranularvariableneighborhoodsearch.
EurJOperRes220(1):15–27LahyaniR,KhemakhemM,SemetF(2016)Aunifiedmatheuristicforsolvingmulti-constrainedtravelingsalesmanprob-lemswithprofits.
EUROJComputOptim.
doi:10.
1007/s13675-016-0071-1LinSW,YuVF(2012)Asimulatedannealingheuristicfortheteamorienteeringproblemwithtimewindows.
EurJOperRes217(1):94–107LourenoH,MartinO,StützleT(2003)Iteratedlocalsearch.
In:GloverF,KochenbergerGA(eds)Handbookofmetaheuris-tics.
Internationalseriesinoperationsresearchandmanagementscience,vol57.
Kluwer,Dordrecht,pp321–353MladenoviN,HansenP(1997)Variableneighborhoodsearch.
ComputOperRes24:1097–1100MontemanniR,GambardellaLM(2009)Anantcolonysystemforteamorienteeringproblemwithtimewindows.
FoundComputDecisSci34(4):287–306MontemanniR,WeylandD,GambardellaLM(2011)Anenhancedantcolonysystemfortheteamorienteeringproblemwithtimewindows.
In:Internationalsymposiumoncomputerscienceandsociety,pp381–384RameshR,BrownKM(1991)Anefficientfour-phaseheuristicforthegeneralizedorienteeringproblem.
ComputOperRes18(2):151–165RighiniG,SalaniM(2009)Decrementalstatespacerelaxationstrategiesandinitializationheuristicsforsolvingtheorien-teeringproblemwithtimewindowswithdynamicprogramming.
ComputOperRes36(4):1191–1203SolomonMM(1987)Algorithmsforthevehicleroutingandschedulingproblemwithtimewindowconstraints.
OperRes35:254–265TaillardED,PBadeauMG,GuertinF,PotvinJY(1997)Atabusearchheuristicforthevehicleroutingproblemwithsofttimewindows.
TranspSci5(2):109–122TasgetirenM(2001)Ageneticalgorithmwithanadaptivepenaltyfunctionfortheorienteeringproblem.
JEconSocRes4(2):1–26ThomadsenT,StidsenT(2003)Thequadraticselectivetravellingsalesmanproblem.
InformaticsandMathematicalMod-elling,TechnicalUniversityofDenmark,DTU,LyngbyTricoireF,RomauchM,DoernerKF,HartlRF(2010)Heuristicsforthemulti-periodorienteeringproblemwithmultipletimewindows.
ComputOperRes37(2):351–367TricoireF,RomauchM,DoernerKF,HartlRF(2013)Addendumtoheuristicsforthemulti-periodorienteeringproblemwithmultipletimewindows.
ComputOperRes40(5)(2013)TsiligiridesT(1984)Heuristicsmethodsappliedtoorienteering.
JOperResSoc35(9):351–367TunchanC(2014)Anartificialbeecolonyalgorithmapproachfortheteamorienteeringproblemwithtimewindows.
ComputIndEng74:270–290Page36of36AghezzafandFahimSpringerPlus(2016)5:1781VansteenwegenP(2008)Planningintourismandpublictransportation.
CentreforIndustrielManagementKatholiekeUniversiteitLeuven,LeuvenVansteenwegenP,OudheusdenDV(2007)Themobiletouristguide:anORopportunity.
ORInsight20(3):21–27VansteenwegenP,SouffriauW,BergheGV,OudheusdenDV(2009)Iteratedlocalsearchfortheteamorienteeringprob-lemwithtimewindows.
ComputOperRes36(12):3281–3290VidalT,CrainicTG,GendreauM,PrinsC(2015)Time-windowrelaxationsinvehicleroutingheuristics.
JHeuristics21(3):329–358