Contributions to rich vehicle routing problems

Cont ribut ions t o rich vehicle rout ing problems

Depart ment of Business and Management Science Norwegian School of Economics

Seyed Most afa Mirhedayat ian

Abstract

T his t hesis addresses rich rout ing problems wit hin a logist ics cont ext . T he first and maj or part of t he t hesis int roduces a new locat ion-rout ing problem , and discusses bot h modeling and solut ion approaches. T he second part addresses t he use of a vehicle rout ing problem in evaluat ing different support ing policies for elect ric vehicles.

Locat ion-rout ing problems have b ecome one of t he most st udied logist ics problems dur ing t he past decade. Recent sur veys on locat ion-rout ing problems have addressed modeling and algorit hmic issues as well as real-life applicat ions, which include for example cit y logist ics, post al and parcel delivery, and grocery dist ribut ion . In t he first part of t he t hesis, mot ivat ed by an act ual problem of a nat ional p ost al service company, we int roduce and define a new t wo-echelon locat ion-rout ing problem (2E-LRP ). T he act ivit ies in t he two echelons are organized int o two waves: a delivery wave where product s are sent from a single primary facility t o cust omers t hrough int ermediat e facilit ies, and a pickup wave where t he flow of product s is reversed . Each echelon has it s own t yp e of vehicles, and we model t he synchronizat ion of t ransshipment s at t he int ermediat e facilit ies. T he model only considers t emporal const raint s, assuming t hat capacit ies are never binding; t he vehicles are always large enough given t he const raint s on t ime. T he result ing problem is a t ime-driven 2E- LRP wit h synchronizat ion and sequent ial delivery and pickup waves. To t he b est of our knowledge, t he problem b eing considered is original b ecause it addresses a new variant of 2E-LRP t hat considers synchronizat ion of t ransshipment s and t he sequence of delivery and pickup act ivit ies.

Because of t he complexit y of t he problem , only small inst ances can b e solved opt imally, and large inst ances cannot even b e solved wit h a feasible solut ion . T herefore, a heur ist ic approach is needed t o t ackle large-size real inst ances. We propose a decomposit ion-based heur ist ic for t he problem and provide comput at ional result s for different set s of inst ances. In addit ion t o t he solut ion approach , we propose dat a-driven schemes for use in combinat ion wit h t he mat hemat ical model. T he aim of t he schemes is t o reduce t he set of feasible solut ions. T he comput at ional result s of t hese schemes are provided for different set s of inst ances.

T he scope of t he second part of t he t hesis is t o illust rat e how a simple vehicle rout ing problem could be used t o enhance economic evaluat ion procedur es of supp ort ing policies for elect ric vehicles. In some count ries, government s have implement ed supp ort ing p olicies for t he use of elect ric vehicles in ur ban freight t ransport . Few st udies have addressed t he impact s of p olicies support ing elect ric vehicles on logist ics and society. To cast light on t his t opic, we est ablish a framework combining an opt imizat ion model (i.e., a vehicle rout ing problem) and economic analysis in order t o det ermine t he opt imal decisions (i.e., purchase and rout ing of vehicles) of an individual logist ics company, and t he result ing changes in ext ernalit ies and welfare in response t o policies designed t o supp ort elect ric vehicles.

K ey words : t wo-echelon locat ion-rout ing, synchronizat ion , pickup and delivery waves, mixed-int eger linear programming, elect ric vehicle, social welfare, ur ban freight policies, het erogeneous vehicle rout ing problem

2

Acknowledgement s

I would like t o express my heart felt acknowledgment t o my sup ervisor P rofessor St ein W . Wallace at t he Depart ment of Business and Management Science, NHH, and my ment or Dr . Mario Guaj ardo, also at t he Depart ment of Business and Management Science, NHH, for t heir cont inuous support of my P h .D, t heir infinit e pat ience and mot ivat ion . T heir guidance helped me t hroughout my research and while writ ing t he t hesis. I could not have imagined having a b et t er sup ervisor and ment or for my P h .D st udy. Special t hanks also go t o P rofessor Teodor Gabriel Crainic at at CIRRELT - t he Int eruniversity Cent re on Ent erprise Net works, Logist ics and Transp ort at ion - and t he School of Management , University of Queb ec in Mont real, Canada , for his precious guidance and support . I also express my deepest t hanks t o P ost en N orge, t he nat ional post al service company in Norway, and it s st aff for providing valuable input s for t he t hesis. Finally, I would like t o express my grat it ude t o my wife, N ahid , and t o my parent s for t heir boundless supp ort and encouragement .

Cont ent s

l Int ro duct ion 1.1 Mot ivat ion . 1.2 Lit erat ur e review 1.3 Cont ribut ions 1.4 Out line . 2 T he m o de l

2.1 P roblem descript ion . 2.2 Model formulat ion . 3 T he so lut io n app roach

3.1 Decomp osit ion-based heur ist ic . 3.1.1 P hase l : Choosing RP configurat ion 3.1.2 P hase 2: Cust omer assignment t o t he RP s 3.1.3 P hase 3: Solving rout ing sub-problem . 4 N um e rical ex p erim e nt s

4.1 Set s of inst ances . . 4.2 P aramet er set t ing . 4.3 Comput at ional result s

4.4 Appendix: charact erist ics of set s of inst ances and det ails of result s .

10 15 18 22 22 24

25 28

37

40 40 42 43 56 57 59 59

69

4

CONT ENT S

5 Sche m e s for t he m o de l

5.1 Reducing t he set of feasible solut ions 5.2 Numerical exp eriments . . · ·

5.2.1 Comput atio n al result s

5.2.2 Ap p endix: det ails of result s wit hout and wit h schemes

6 E x t e nsio n

6.1 P roblem descript ion . 6.2 Model formu latio n .

77 77 81 81 85

90

91 92

7 A fr am e work t o eva luat e p o licy opt ions for e le ct ric ve hicle s 7. 1 Lit er at ur e review

7.2 A framework for p olicy evalu at ion 7.2. 1 Scen arios

7.2.2 Opt imizat ion model . 7.2.3 Econom ic an alysis 7.3 Numerical exp eriment s

7.3. 1 P roblem inst ances . 7.3.2 Com put at ion al result s 7.3.3 Sensit ivity an alysis 7.4 Conclusions

101 105 107 108 109 114 118 119 121 124 125 7.5 App endix: det ails of result s obt ained from t ax ch anges and sensit ivit y an al-

y SI S 127

8 Co ncl usio ns and fut ure work R efere nce s

132 136

List of Tables

2.1 Set s, paramet ers, and variables used in t he MILP model . . . 30 3.1 Set s, paramet ers, and decision variables used in t he assignment model . 42 3.2 Set s, paramet ers, and variables used in t he set-part it ioning model 49 3.3 Set s and paramet ers used in t he decomposit ion-based heur ist ic 55 4.1 Aggregat ed result s obt ained by different approaches . . . 61 4.2 Aggregat ed result s for different numbers of local search sub-it erat ions 65

4.3 Charact erist ics of inst ances in Sil 70

4.4 Charact erist ics of inst ances in SI2 4.5 Charact erist ics of inst ances in SI3 4.6 Charact erist ics of inst ances in SI4 4. 7 Det ailed result s for Sil

4.8 Det ailed result s for SI2 4.9 Det ailed result s for SI3 4.10 Det ailed result s for SI4

4.11 Det ailed result s for different numb ers of local search sub-it erat ions . 5.1 Aggregat ed result s for Sil wit hout and wit h t he schemes

5.2 Aggregat ed result s for SI2 wit hout and wit h t he schemes 5.3 Aggregat ed result s for SI3 wit hout and wit h t he schemes

70 70 71 72 73 74 75 76 82 83 83

6

LIST OF TABLES

5.4 Aggregat ed result s for SI4 wit hout and wit h t he schemes 5.5 Det ailed result s for Sil wit hout and wit h t he schemes 5.6 Det ailed result s for SI2 wit hout and wit h t he schemes 5.7 Det ailed result s for SI3 wit hout and wit h t he schemes

84 86 87 88 5.8 Det ailed result s for SI4 wit hout and wit h t he schemes 89 6.1 Set s, paramet ers , and variables used in t he MILP model (mult i-t erminal) 94 7.1 Set s, paramet ers , and variables used in t he MILP model for t he zone-dep endent

vehicle rout ing problem wit h a mixed fleet 7.2 Vehi cle charact erist ics

7.3 Dat a for variables . . .

112 120 121 7.4 Impact s of different EV-support ing policy opt ions on company's decisions

and social welfare . · · . · . · · . . . · · . · . · . . . . · . . . . · . · . . . . 123 7.5 Imp act s of different EV-support ing policy opt ions wit h different pur chase

subsidy . . · · · . · · . . . · · . · · · . 127 7.6 Impact s of different EV-support ing p olicy opt ions wit h different zone fees 128 7.7 Impact s of different EV-support ing p olicy opt ions wit h different vehicle t axes 129 7.8 Imp act s of different EV-supp ort ing policy opt ions for EVs wit h an ext ended

driving range . . · . · . . · . · . . . . · . . . . · . · . . . . · . · . · · . . . 130 7.9 Impact s of different EV-support ing p olicy opt ions for EVs wit h a larger car-

rying capacit y . . · · · · . . . . · . . · . . . · . . · . · . . . 130 7.10 Impact s of different EV-support ing policy opt ions wit h a smaller diesel vehicle 131 7.11 Impact s of different EV-support ing p olicy opt ions for a smaller cit y . . . 131 7.12 Imp act s of different EV-support ing policy opt ions for a city wit h larger demands 131

GB K

LIST OF FIGURES

7.1 Framework for evaluat ing t he impact s of policies on t he logist ic cost s of a company and social welfare .

7.2 Illust rat ion of t he first and second levels 7.3 Feasible solut ion for t he t ransport network

7.4 Welfare changes corresponding t o changes in t he daily t ax rat e

108

110 119 124

Chapt er l Int roduct ion

Logist ics problems deal wit h st rat egic, t act ical and operat ional decisions wit hin dist ribut ion syst ems. St rat egic decisions concern long-t erm issues such as decisions on type, numb er and locat ion of facilit ies, as well as decisions on t yp e and size of vehicle fleet . At t he t act ical level, t ypical decisions are on cust omer-visit frequencies and order t ype in a given t ime horizon . T he operat ional level deals wit h dist ribut ion planning act ivit ies including vehicles and t he drivers' schedules. At t his level, short -t erm and daily decisions such as rout ing of vehicles are made.

Vehicle rout ing problems (VRP s) have been one of t he most cit ed logist ic problems in t he lit erat ur e dur ing t he five past decades. T he original VRP was int roduced in a paper by Dant zig and Ramser (1959) and it t ackles t act ical and op erat ional level decisions. T he VRP is defined in a dist ribut ion syst em where a given set of cust omers wit h delivery demands is served from a single facilit y using a given set of vehicles. T he aim of t he VRP is oft en t o minimize t ot al dist ance. In it s st andard form , each cust omer must be visit ed by exact ly one vehicle and each vehicle performs a single t rip st art ing and ending at a facilit y. T he decisions in t he VRP are t o assign cust omers t o each vehicle and t o det ermine t he order of cust omer visit s by each vehicle.

10

CHAP T ER l. INT RODUCT ION

In dist ribut ion syst em s design , decisions on facilit y locat ions (e.g.,plant s, dep ot s , ware- houses and hubs) are relevant due t o t heir imp act on t ot al dist ribut ion cost s and service m easur es. Despit e t he fact t h at such locat ion decisions are oft en st r at egic, it is crucial t o capt ur e t heir int er act ions wit h t he op er at ion of t he net work . T his h as mot ivat ed a growing b ody of lit er at ur e on locat ion-rout ing problem s (LR P s) , which combine locat ion and rout - ing decisions. In t he st and ard LR P , a given set of cust omers wit h known delivery dem ands is served from a set of p ot ent ial facilit ies using a given set of vehicles . An op ening cost is assigned t o each facilit y. T he aim is t o m inimize over all cost s consist ing of b ot h rout ing and facility op ening cost s . T he decisions in t he LR P are t o det ermine t he locat ions of t he facilit ies, t o assign cust om ers t o each facilit y and t o det ermine t he vehicles' rout es.

T he combin at ion of different feat ur es, such as vehicles cap acit ies, rout es lengt hs and t ime windows, h as result ed in a variet y of LR P s, as recent ly reviewed in sur vey p ap ers by Nagy and Salhi (2007) , P rodhon and P rins (2014) and Drexl and Schneider (2015) . Among t hese, t he lit er at ur e on two-echelon locat ion-rout ing problems (2E-LR P s) and it s variant s is scarce.

T he 2E-LR P is defined in a two-echelon dist ribut ion syst em . In two-echelon dist ribut ion syst ems, product s are t r ansp ort ed from origins (e.g., suppliers or product ion plant s) t o dest in at ions (e.g. , cust om ers or ret ailers) , t hrough int erm ediat e facilit ies (e.g.,dep ot s, cross- docks or dist ribut ion cent ers) where different op er at ions such as st or age, consolid at ion or t r ansshipment occur. In 2E-LRP s , t wo echelons int er act t hrough int ermediat e facilit ies , where t he first echelon consist s of prim ary and int erm ediat e facilit ies, and t he second echelon consist s of t he int ermediat e facilit ies and cust omers . Each echelon h as it s own t yp e of vehicles. T he aim is t o decide on locat ion of cent r al or int ermediat e facilit ies ( or b ot h ) , in addit ion t o rout ing wit hin each echelon . T he m ain quest ion t h at arises in a t wo-echelon dist ribut ion syst em is how t o synchronize t he flows of two echelons at int ermediat e facilit ies.

T he synchronizat ion is imp ort ant due t o st or age lim it at ion at t he int erm ediat e facilit ies and t ime windows for visit ing t he cust omers . In it s st and ard form , t he 2E-LR P assum es t h at cust omers only require deliveries. However , in pr act ice, cust om ers oft en need b ot h pickup

CHAP T ER l. INT RODUCT ION

and delivery. T his may be t he case in many real-life applicat ions such as cit y logist ics and post al and parcel delivery.

T his t hesis addresses rich vehicle rout ing problems wit hin a logist ics cont ext . T he t erm rich vehicle routing is associat ed wit h problems t hat incorp orat e some or all complex at - t ribut es ofr eal-life applicat ions. Some examples for such at t ribut es are t emp oral const raint s, sequence of dist ribut ion act ivit ies, fleet het erogeneit y, diversit y of policies, and environmen- t al issues (Caceres-Cruz et al., 2015) . Survey papers on rich vehicle rout ing problems are provided by Drexl (2012) ; Lahyani et al. (2015) ; Caceres-Cruz et al. (2015) , and int erest ed readers may refer t o t hese pap ers

T he first and bulk part of t he t hesis int roduces a new locat ion-rout ing problem and discusses bot h modeling and solut ion approaches. Mot ivat ed by an act ual problem of t he post al service company in Norway, we int roduce a new 2E-LRP. Th e act ivit ies are organized in t wo waves: a delivery wave, where product s are t ransport ed from a single primary facility t o int ermediat e facilit ies and from int ermediat e facilit ies t o cust omers , and a pickup wave, where t he flow of product s is reverse. T he cust omers in each wave are served wit hin individ- ual t ime windows and t he synchronizat ion of t ransshipment s at t he int ermediat e facilit ies is resp ect ed . T he decisions in t he problem is t o det ermine t he locat ions of int ermediat e facilit ies and t he vehicle rout es at each echelon . We consider only t ime-relat ed quest ions.

T his is t ypical for some p ost al and parcel delivery syst ems where t he delivery and pickup of product s out side densely p opulat ed areas are uniquely governed by t ime: when product s are available at t he primary facilit y, driving t imes t o int ermediat e facilit ies, synchroniza- t ion of vehicles at t hese facilit ies, and t he delivery t ime t o cust omers . And t hen t he same sequence in t he aft ernoon , ending wit h t he lat est arrival t ime of product s at t he primary facilit y. Wi t hin t his framework , all vehicles are assumed t o be large enough . Alt hough t his is not always t rue, it is most of t he t ime. T he result ing problem is a t ime-driven 2E- LRP wit h synchronizat ion and sequent ial delivery and pickup waves. Most papers st udying 2E-LRP s ignore t he synchronizat ion of t ransshipment s at t he int ermediat e facilit ies (Drexl

12

CHAP T ER l. INT RODUCT ION

and Schneider, 2015) . To t he b est of our knowledge, t ime windows and synchronizat ion have not been st udied t oget her in t he lit erat ur e on 2E-LRP and , in fact , a sur vey paper on t wo-echelon rout ing problems by Cuda et al. (2015) highlight s t hese asp ect s as wort hwhile t o invest igat e. Weprovide a mixed-int eger linear programming (MI LP ) formulat ion for t he problem t hat we int roduce.

Nagy and Salhi (2007) classifi ed LRP s in t erms of four key asp ect s; st ruct ure (i.e., st an- dard hierarchical or non-st andard hierarchical) , type of input dat a (i.e., det erminist ic or st ochast ic) , planning period (i.e. ,single- or mult i-period), and solut ion met hods (i.e., exact or heuristi c). In st andard hierarchical LRP s, facilit ies serve cust omers t hat are connect ed t o t he facilit ies by means of vehicle t our s and no t our connect s facilit ies. T he main difference bet ween st andard and non-st andard hierarchical LRP s is t he incorporat ion of t our planning in different layers (i.e .,echelons) . Some example of non-st andard LRP s are transportation- location p roble m (e.g., Cooper (1972) ; Klibi et al. (2010)) wh ere t he t our planning is not involved , m an y-t o-m an y location-routing p roblem (e.g.,Nagy and Salhi (1998) ; Wasner and Zäpfel (2004)) wh ere t our planning is involved in b ot h int er-facilit ies rout ing and between cust omers and facilit ies rout ing, vehicle routing-allocation p roblem (e.g.,Beasley and Nasci- ment o (1996)) where int er-facilit ies t our planning is involved but t our planning between cust omers and facilit ies is excluded , and m ulti-level location -routing p roblem t hat may in- clude t our-planning wit hin each layer. Based on t he classificat ion of LRP s provided by Nagy and Salhi (2007), t he problem t hat we int roduce in t he t hesis is cat egorized as determ in istic single-p eriod n on-stan dard hierarchical LR.P.

T he 2E-LRP and it s variant s are very hard opt imizat ion problems and seldom invest i- gat ed (P rodhon and P rins, 2014) . Due t o t he complexity of t he problem , only very small 2E-LRP inst ances can be solved using exact approaches. T herefore, heur ist ics are required t o obt ain appropriat e solut ions in accept able running t imes on t he large inst ances t hat can be found in pract ical applicat ions. In t his t hesis, we propose a decomposition-based heuristic for t he t ime-driven 2E-LRP wit h synchronizat ion and sequent ial delivery and pickup waves.

CHAP T ER l. INT RODUCT ION

T he decomp osit ion-based heur ist ic decomp oses t he problem int o t hree phases: l ) choosing t he facility configurat ion, 2) assigning t he cust omers t o t he chosen facilit ies and 3) solvi ng t he rout ing sub-problem . Wep erfo rm numerical experiment s t o check t he performance of t he decomposit ion-based heur ist ic in t erms of t he solut ion qualit y and comput at ional t ime for different set s of inst ances. We compare t he effect of t he first phase of t he proposed approach on t he solut ion quality t o t he common approach used in t he lit erat ur e for facility configur at ion .

Besides t he solut ion approach , we propose different schemes t hat work in combinat ion wit h t he MILP formulat ion . T he aim of t he schemes is t o reduce t he feasible solut ion space by removing rout es t hat are unlikely t o be part of high qualit y solut ions. T hrough numerical exp eriment s, we check t he effect of schemes on reducing t he set of feasible solut ions for different set s of inst ances.

Logist ics problems (e.g., vehicle rout ing problems, locat ion-rout ing problems) usually focus on dist ribut ion cost minimizat ion (e.g., facility opening cost s, rout ing cost s) . In- corporat ing sust ainability issues in logist ics problems poses t he challenging field of green logistics,which has received considerable at t ent ion from researchers in recent decades (Lin et al., 2014). Green logist ics concern environment al, ecological and social issues as well as ot her convent ional economic cost s wit hin dist ribut ion syst ems. T he aim of green logist ics is t o obt ain a sust ainable dist ribut ion syst em by considering environment ally sensit ive t rans- port at ion p olicies. Such policies encour age companies t o use green vehicles (i.e., vehicles wit h less negat ive environment al effect s) such as elect ric vehicles (EV) for t ransport at ion needs.

Cont rary t o t he first part of t he t hesis where we address different aspect s of an act ual problem t hrough an opt imizat ion model, in t he second part of t he t hesis, we do not aim t o int roduce a new rout ing problem but t he scop e is t o illust rat e how a simple vehicle rout ing problem could b e used t o enhance economic evaluat ion procedur es of support ing policies for elect ric vehicles. Despit e growing research int erest in ur ban freight t ransp ort , t here have

14

CHAP T ER l. INT RODUCT ION

been few st udies addressing t he impact s of EV-supp ort ing policies on logist ics and societ y.

As a cont ribut ion t o cover t he gap , we est ablish a framework t hat combines an opt imizat ion model (i.e., a vehicle rout ing problem ) and economic analysis t o evaluat e t he impact s of EV-support ing policies on an individual company's logist ics decisions (i.e., vehicle rout ing and pur chase) and corresponding changes in ext ernality and welfare.

In t he reminder of t his chapt er , we explain t he act ual problem t hat mot ivat ed us t o int roduce t he new 2E-LRP, we review t he lit erat ur e relat ed t o t he new problem and out line t he cont ribut ions of t he t hesis b efore present ing an overview of t he dissert at ion .

1.1 M ot ivat ion

Our main mot ivat ion comes from an act ual problem arising in P ost en N orge, t he nat ional post al service company in Norway. T his company provides mail and package delivery ser- vices via t wo main brands: P ost en and B ring. Post en focuses on serving p ost offices and small post cent ers locat ed in select ed local supermarket s, while Bring focuses on business cust omers such as privat e companies and organizat ions in t he Nordic area . A maj or concern for all post al service companies is t o provide cust omers wit h on-t ime services while using resour ces efficient ly. T he most not able obst acle in Norway is t he geographical locat ion of cust omers . Norway is a relat ively long count ry, wit h an int ricat e geography including more t han 25,000 km of coast line and a numb er of small t owns in ur ban and rural regions.

P roviding coverage across t he whole count ry p oses a challenge t o post al service companies.

T he main facilit ies for a post al service company are t erminals. Post en Norge has ninet een t erminals spread around Norway, as shown in Figure 1.1. Each cust omer is assigned t o a unique t erminal. A t erminal is a place where goods, previously picked up from cust omers , are sort ed before b eing delivered t o t he final cust omers . All goods must pass t hrough a t erminal for dat a capt ur ing pur poses.

Cust omers locat ed close t o a t erminal are served direct ly from t he t erminal. For cus-

CHAP T ER l. INT RODUCT ION

t omers fart her away (i.e., t ypically locat ed in rural areas), it is inefficient t o serve t hem direct ly from t he t erminal. It would be t oo expensive t o use small vehicles as t he number of necessary vehicles would be very large due t o t ime windows of visit ing cust omers and limit ed sp eed of vehicles. Large vehicles, on t he ot her hand , would have limit at ions in rural areas due t o feat ur es such as narrowness or st eepness of roads, as well as t he dist ances between cust omers ; a full large vehicle would t ake far t oo long t o deliver all it s goods wit hin t he t ime windows. One reasonable solut ion t o t his problem is t o est ablish reloading point s between t he t erminal and cust omers . T hese p oint s serve as locat ions where goods are unloaded from large vehicles, coming from t he t erminal and reloaded ont o small vehicles, depart ing t o cust omers . Post en Norge is cur rent ly looking for t he opt imal locat ion of reloading p oint s (RP s) associat ed t o each of it s t erminals. Figure 1.2 illust rat es t he geographical dist ribut ion of cust omers and p ot ent ial sit es of RP s for a specific t erminal. T he square represent s t he t erminal, t he t riangles are t he p ot ent ial sit es for reloading point s, and t he grey dot s are cust omers .

16

CHAP T ER l. INT RODUCT ION

. . , ... .., (IIMa

uor oll

t.

oton ll pg. w r ;l,-

i i s«e

El i@eland

..

^-

llllttoncl'ielrn

Åle5,11tit8 (Mo lde

soenoe:

Sel'f:li:tl F;ord rllt ømm..1r tlaugaund ffrarrim41n'"

Stavangerll s oddly] r eankst ad

Kuti6ans.saDl

El Ter i al

Figur e l .l : Geographical dist ribut ion of t erminals wit hin Norway

• Customer

l:::,.Potential sites for reload ing points Terminal

II.

..

..

• Dra mmes •

.J,, .. . · • ••L, ·

F igure 1.2: Geographical dist ribut ion of cust omers and p ot ent ial sit es of RP s for t he Dram- men t erminal

CHAP T ER l. INT RODUCT ION

1.2 Lit erat ure rev iew

T he lit er at ur e on t wo-echelon rout ing problem s can b e split in t wo classes: t he 2E-LR P and t wo-echelon vehicle rout ing problems (2E-VR P ) . Int erest ed readers are referr ed t o recent sur veys (Drexl and Schneider , 2015; P rodhon and P rins, 2014; Cud a et

al.,

2015) . In a 2E-VR P , t he set of prim ary and int ermediat e facilit ies is given (i.e., t here is no decision on t he locat ion of facilit ies) and t he aim is t o decide on vehicles rout es in b ot h echelons.

Bot h 2E-LRP and 2E-VR P can b e applied t o many real-life problems such as cit y logist ics and p ost al and p arcel delivery. In t he lit er at ur e, cit y logist ics is prob ably t he most cit ed applicat ion . Here we examine t he relevant lit er at ur e on t wo-echelon rout ing problem s, in t he cont ext of p ost al service design and city logist ics and we focus on p ap ers t h at sp ecifically consider wh at is imp ort ant t o us; t emp or al consider at ions, such as synchronizat ion , t ime windows, and sequencing of deliveries and pickups.

A sm all b ody of lit er at ur e addresses t he applicat ion of LR P s on p arcel delivery. Am ong t hese, t he p ap ers by Bruns et al. (2000) ; Wasner and Zäpfel (2004) ; W inkenb ach et

al.

(2015, 2016) are wort h ment ioning . Bruns et al. (2000) investig at ed t he problem of p ost al service net works . In t heir problem , t he dist ribut ion network consist s of t hree echelons and four levels. T he first level consist s of p ost offices. T he second and t he t hird levels consist of p arcel processing cent ers and delivery b ases, resp ect ively. T he fourt h level consist s of cust omers wit h delivery dem ands . T he p arcels are delivered from p ost offices t o p arcel processing cent ers and t hen t o delivery b ases , and from t he delivery b ases t o cust omers . Alt hough t he origin al problem is a mult i-echelon LR P , it is convert ed t o an LRP by fixing t he locat ions of t he p arcel processing cent ers and allocat ing delivery b ases t o p arcel processing cent ers . T he cust om ers are p art it ioned int o different zones, and t he rout ing cost s for each zone are approxim at ed . In t his m anner , t he LR P is reduced t o a facility locat ion problem , where t he aim is t o decide on t he locat ion of t he delivery b ases and allocat ion of cust om er zones t o delivery bases. Wasner and Zäpfel (2004) st udi ed a problem p osed by a p arcel delivery service provider in Aust ria . In t heir problem , t he cust omers have b ot h delivery

18

CHAP T ER l. INT RODUCT ION

and pickup demands. T he pickup and delivery flows of product s b et ween cust omers must pass t hrough hubs. A cent ral hub wit h known locat ion is given , and all ot her hubs are connect ed t o each ot her t hrough t he cent ral hub . T he problem is considered as a hub- locat ion vehicle rout ing problem , where t he aim is t o decide on t he locat ion of t he hubs excluding t he cent ral hub as well as t he int er-hub and hub-t o-cust omer rout ing. T he main difference between hub-location routing p roblem s and LRP s is t hat in t he former , besides t he int eract ions b et ween hub facilit ies and cust omers , t he int eract ions (i.e., flow) between t he hubs t hemselves is considered (Aykin, 1995) , while t his is not t he case for t he lat t er. In a recent paper, Winkenbach et al. (2015) develop ed an opt imizat ion model for t he nat ional post al operat or in France. T he opt imizat ion model enables decision makers t o est ablish single-echelon or t wo-echelon ( or bot h) syst ems in order t o serve cust omers demanding different t yp es of product s. T he aim of t he opt imizat ion model is t o ident ify t he opt imal number and locat ions of facilit ies at each echelon , t he opt imal sizes and shapes of areas assigned t o each facilit y, and t he opt imal fleet size. T he minimal rout ing cost s of t he vehicles are approximat ed wit h regards t o different const raint s involving t he vehicle capacity and maximum rout e lengt h . T he approximat ion formula is used in t he proposed MILP formulat ion for t he 2E-LRP . Th ey t est ed t he validit y of t he approximat ion formula and observed high-quality solut ions wit hin a reasonable t ime for large-scale inst ances.

Regarding t he t emporal aspect s in 2E-LRP, t here are few papers in t he lit erat ur e.

Nikbakhsh and Zegordi (2010) considered a 2E-LRP where soft t ime windows are applied t o serving cust omers wit h a penalty for violat ion . T he aim of t he problem is t o decide t he locat ion of int ermediat e facilit ies as well as rout ing of vehicles in bot h echelons. T he syn- chronizat ion of t ransshipment s at int ermediat e facilit ies is not considered . T hey proposed a t hree-index MILP formulat ion while showing how t o comput e a lower b ound for t he problem and provided a two-st age heur ist ic.

A few pap ers in t he lit erat ur e address t he applicat ion of two-echelon rout ing (e.g.,2E- VRP, 2E-LRP ) in cit y logisti cs (e.g., Crain ic et al. (2011) and Perboli et al. (2011)) . In

CHAP T ER l. INT RODUCT ION

t wo-echelon (also known as two-t iered) city logist ic problems, t he first echelon involves pri- mary vehicles wit h larger capacit ies delivering product s from primary facilit ies locat ed on t he out skirt s of t he cit y t o int ermediat e facilit ies where product s are t ransferred t o sec- ondary vehicles wit h smaller capacit ies p erforming t he int ermediat e facilit ies-t o-cust omers delivery rout es. In t he cont ext of city logist ics, different variant s such as synchronizat ion of t ransshipment at int ermediat e facilit ies, and t ime windows, can be adapt ed . Crainic et al. (2009) int roduced a new problem class wit hin t wo-echelon city logist ics problems t hat consider vehicle depart ur e scheduling, st rict t ime synchronizat ion of t ransshipment at int er- mediat e facilit ies, and t he t ime windows of cust omers . T he problem concerns t he select ion of rout es and scheduling of depart ur es for t he vehicles in each echelon , as well as t he select ion of delivery rout es for t he cust omer demands from t he primary facilit ies t hrough int erme- diat e facilit ies t o t he final cust omer. T hey provided a general mat hemat ical formulat ion for t he problem . Crainic et al. (2012) discussed met hodological and managerial challenges relat ed t o t he int egrat ion of different t yp es of t raffic st rat egies wit hin t he two-echelon city logist ics problem . T hey considered t hree t ypes of t raffic st rat egies: cust omer-t o-cust omer (c2c) , cust omer-t o-ext ernal zone (c2e) , and ext ernal zone-t o-cust omer (e2c) . T he c2c st rat - egy concerns t he t raffic of vehicles bet ween cust omers inside cit y limit . T he c2e st rat egy incorp orat es t raffic of vehicles from cust omers inside t he cit y limit t o zones out side t he city limit . T he e2c st rat egy deals wit h t raffic of vehicles from zones out side t he city limit t o cust omers inside. Cust omers can have bot h delivery and pickup demands, and t his makes t he int egrat ion of different st rat egies complex . In order t o avoid int erlacing t he pickup and delivery operat ions, t hey int roduced a simple st rat egy, called p s eudo-backhaul, where a rout e must be complet ed b efore t he next rout e st art s. Following t he concept s relat ed t o int egrat ion of t hree t yp es of t raffic st rat egies (Crainic et al ., 2012) , Crainic et al. (2016) formally int roduced and defined t he new variant of 2E-VRP, where t hey considered different variant s such as mult iple rout es of vehicles, synchronizat ion of t ransshipment at facilit ies, sequences of delivery and pickup operat ions, and t ime dep endency of t ravel. Vehicles per-

20

CHAP T ER l. INT RODUCT ION

form mult iple rout es; each rout e consist s of a sequence of visit s at facilit ies and cust omers at given t ime moment s. T he mult iple rout es of each vehicle follow t he pseudo-backhaul st rat egy. T he rout es serving t he c2c request s follow t he last -in-first -out rule, and t he st rict t ime synchronizat ion at facilit ies is considered .

Regarding t he sequence of delivery and pickup act ivit ies, Parr agh et al. (2008) classifi ed t he vehicle rout ing problems int o two main classes. T he first class is denot ed as vehicle rout ing problems wit h backhauls, where delivery cust omers are served in t he linehaul and pickup cust omers are served in t he backhaul. T he significance of t his problem comes from using t he free capacity in vehicles when ret urning (backhaul) t o t he facilit ies. Two main variant s of vehicle rout ing wit h backhauls are vehicle routing with clustered backhaul, where all linehauls are before backhauls, and vehicle routing with mixed linehauls and backhauls , where any sequence of linehauls and backhauls is permit t ed . T he second class deals wit h t ransp ort at ion of product s between delivery and pickup locat ions and is denot ed as pickup and delivery vehicle rout ing problems. T he pseudo-backhaul st rat egy considered by Crainic et al. (2016) is different from t he problem considered in t his t hesis wit h respect t o t he sequence of delivery and pickup act ivit ies. In t he former , alt hough t he mult iple rout es of t he vehicles follow t he pseudo-backhaul st rat egy, t he last -in-first -out rule applied t o visit ing c2c request s may cause a rout e p erforming such request s consist of a sequence of visit s at delivery and pickup cust omers t hat does not follow t he rules in t he vehicle rout ing problem wit h backhaul. T he pickup and delivery waves in t he problem considered in t his t hesis are similar t o linehauls and backhauls in vehicle rout ing problems wit h clust ered backhauls (Goet schalckx and J acobs-Blecha, 1989) , where all deliveries must b e made before t he pick- ups as dict at ed by our mot ivat ion example.

Regarding t he relat ed lit erat ur e, t he problem t hat we consider is original since it ad- dresses a new variant of 2E-LRP t hat incorporat es synchronizat ion of t ransshipment and sequence of delivery and pickup act ivit ies.

•

•

•

•

CHAP T ER l. INT RODUCT ION

heuristic. Chapt er 5 proposes t hree schemes in order t o reduce t he set of feasible solut ions, and checks t o what ext ent t he schemes help wit h finding bet t er solut ions in less t ime for t he set s of inst ances provided in Chapt er 4. Chapt er 6 ext ends t he problem discussed in Chapt er 2 t o incorporat e t he vehicles capacit y, mult iple t rips for vehicles, and locat ion decisions on t erminals. Chapt er 7 provides a framework combining an opt imizat ion model and economic analysis for evaluat ing t he effect of EV-support ing policy changes on result ed welfare. Chapt er 8 concludes t he t hesis, and discusses possible futur e research direct ions.

Chapter 2 The model

Mot ivat ed by t he act ual problem discussed in Chapt er l , here we int roduce and define a new t wo-echelon locat ion-rout ing problem (2E-LRP ) . T he problem is defined wit hin a t wo-echelon dist ribut ion syst em , where t he first echelon comprises a single t erminal as t he primary facilit y and reloading p oint s (RP s) as int ermediat e facilit ies, and t he second ech- elon consist s of RP s and cust omers. T here are two waves: delivery, where product s are t ransp ort ed from t he t erminal t o RP s and from RP s t o cust omers; and pickup , where t he flow of product s is reversed . T he cust omers in each wave are served wit hin individual t ime windows, and t he synchronizat ion of t ransshipment s at t he RP s is respect ed .

Locat ion-rout ing problems are normally const rained by t ime and capacit y. We consider only t ime-relat ed quest ions. T his is t ypical for some p ost al and parcel delivery syst ems where t he delivery and pickup of product s out side densely p opulat ed areas are uniquely governed by t ime: when product s are available at t he t erminal, driving t imes t o int ermediat e facilit ies, synchronizat ion of vehicles at t hese facilit ies, and t he delivery t ime t o cust omers. And t hen t he same sequence in t he aft ernoon , ending wit h t he lat est arrival t ime of product s at t he t erminal. Wit hin t his framework, all vehicles are assumed t o be large enough . Alt hough t his is not always t rue, it is most of t he t ime. T his means t hat one (lar ge) vehicle is enough t o deliver product s t o t he int ermediat e facilit ies. However , because of t he driving t ime, t he

24

CHAP TE R 2. T HE MODEL

arrival at RP s leaves very lit t le t ime for deliveries in t he second echelon . T hus, t here is a t radeoff between t ime spent in t his echelon and t he numb er of vehicles. For delivery t o cust omers , t he available t ime is limit ed , and t he number of deliveries (and lat er pickups) t hat can be made imply t hat vehicles are never full. T his also means t hat each vehicle in t his second echelon makes only one t our because t here is no reason t o go back t o t he int ermediat e facilit ies. T his could be a pur e delivery t our , pur e pickup t our , or as is t he case most of t he t ime, a combined t our where pickups follow deliveries. T his is what tim e-driven means: t he problem is only governed by t ime, not volume and capacity.

T he rest of t his chapt er is organized as follows. Sect ion 2.1 describ es t he t ime-driven 2E- LRP wit h synchronizat ion and sequent ial delivery and pickup waves. Sect ion 2.2 present s a mixed-int eger linear programming (MILP ) formulati on for t he problem .

2 .1 P roblem descript ion

W e consider a two-echelon dist ribut ion syst em consist ing of t hree levels. T he first level cont ains a single t erminal. T he second level consist s of RP s as int ermediat e facilit ies, while t he t hird level consist s of cust omers . T he first echelon comprises t he t erminal and RP s, and t he second echelon comprises t he RP s and cust omers . T he following not at ion is used .

W e assume a single product ; t his is t ypically post al packages. T he termin al is t he primary facilit y; it is generally locat ed in an ur ban area and is a place where product s previously picked up from cust omers are sort ed b efore being delivered t o cust omers . T he product s must pass t hrough t he t erminal for dat a capt ur ing pur poses. Prim ary vehicles are large vehicles t hat t ransp ort product s wit hin t he first echelon . S econdary vehicles are smaller vehicles t hat t ransport product s wit hin t he second echelon . R Ps are int ermediat e facilit ies t hat are meet ing p oint s for primary and secondary vehicles so t hat t hey can t ransfer product s. T he product s can be st ored in RP s for short p eriods t o b e t ransferred b et ween primary and secondary vehicles. No ot her op erat ions, such as long-t erm st orage or any ot her processes

CHAP TE R 2. T HE MODEL

t hat may change t he shape and form of product s, t ake place at t he RP s. Custom ers are t he final dest inat ions wit hin t he dist ribut ion syst em . For post al syst ems, t hese are typically post offices, post in st ores, companies, or individuals.

Here, we only consider cust omers locat ed far away from t he t erminal; t his is t ypical in rural areas. Cust omers t hat live close t o t he t erminal, which is typical for more densely populat ed areas, are served direct ly from t he t erminal and are t herefore not covered by t he t wo-echelon model.

It is inefficient t o serve t hese rural cust omers direct ly from t he t erminal. It is t oo exp ensive t o use secondary vehicles because t he necessary number of vehicles is very large;

a large number of sm all vehicles will need t o t ravel a long way, and t hey will not be full even t hough t hey are small because t hey would have very limit ed t ime for t he act ual delivery.

On t he ot her hand , primary vehicles would encount er limit at ions in rural areas such as narrow or st eep roads as well as t he dist ances b et ween cust omers . A full primary vehicle will t ake far t oo long t o deliver all of it s product s. Hence, it is beneficial t o est ablish RP s as locat ions where product s are unloaded from primary vehicles coming from t he t erminal and reloaded ont o secondary vehicles depart ing t o cust omers . In t his manner , primary vehicles can efficient ly t ransport large volumes from t he t erminal t o t he RP s, and secondary vehicles can efficient ly handle smaller volumes of product s in rural areas, which generally include narrow or st eep roads. Organizing t hese different vehicles in two echelons may also be an environment ally friendly solut ion , as p oint ed out by Mancini (2013) .

T he cust omers are served in two waves: delivery and pickup . In t he delivery wave, product s are sent from t he t erminal t o RP s by primary vehicles and from RP s t o cust omers by secondary vehicles. In t he p ickup wave, product s collect ed from cust omers are sent t o RP s by secondary vehicles and t hen from RP s t o t he t erminal by primary vehicles. We model t he swit ch from delivery t o pickup by let t ing a secondary vehicle pass from a delivery cust omer t o a pickup cust omer once at most ; t he reverse is never allowed . T ime windows for visit ing t he cust omers in each wave are also given . T hese can be used in t wo different ways.

26

CHAP T ER 2. T HE MODEL

F irst , t hey can be used t o ensur e t hat not only does each vehicle perform deliveries before pickups but also t hat all deliveries t ake place before any pickup . Second , t ime windows can nat ur ally also be used t o express t hat cert ain cust omers must be served wit hin specific cust omer-defined t ime windows.

•

Customer in delivery w ave Terminal

0

Customer in pickup wave

A

Reloading point Route in delivery wave

.-A

Primary vehicle

-

- - - - Route in pickup wave

e

Secondary vehic le

F igur e 2.1: Illust rat ion of t he first and second echelons

F igur e 2.1 illust rat es an example of t he t wo echelons. T he square represent s t he t erminal, and t he t riangles are t he RP s. T he rout es in t he delivery wave are illust rat ed wit h solid lines, while t he rout es in t he pickup wave are illust rat ed wit h dashed lines. T he black circles represent cust omers in t he delivery wave, and t he whit e circles are cust omers in t he pickup wave. P rimary and secondary vehicles make t ours wit hin t heir echelons. Each secondary

G(V, A) V

A V = V¹ V² V¹ = O R

O R

V² = R J^D J^P J^D J^P

A = A¹ A² A¹= { (i , j )|i O R, j O R, i = j }

A²= { (i , j )|i V², j V²\ { { (g, h)|g J^P, h J^D} { (m, n)|m R, n R} } }

A² g J^P

h J^D

T_{i j}^e

i j e (i , j ) A^e, e E E = { 1, 2}

A^e e E c^e_{i j}

(i , j ) A^e

r R fr J = J^D J^P

j J [aj, bj]

aj bj j J L

K T^{z er o}

T^{f i n} f ^e

e E

zr { 0, 1} , r

R r

x¹_{i j l} x²_{i j k}

x¹_{i j l} { 0, 1} , (i , j ) A¹, l L (i , j )

l x²_{i j k} { 0, 1} , (i , j ) A², k K (i , j )

k

t¹_{i l} 0, i V¹, l L i t^end_l 0, l L

l t² 0, i J i t^d 0, r

k r

ur k l { 0, 1} , r R, k K , l L

k l r

O O = { o}

T^{z er o} T^{f i n} R

f_r r r R

E E = { 1, 2}

A^e e e E

T_{i j} ^e i j e (i , j ) A^e, e E

c^e_{i j} (i , j ) e (i , j ) A^e, e E

J^D J^P

J J = J^D J^P

aj j j J

b_j j j J

L K

f^e e e E

M

zr { 0, 1} r r R

x¹_{i j l} { 0, 1} (i , j )

l l L , (i , j ) A¹

t¹_{i l} 0 l i l L , i V¹

t^end_l 0 l l L

x²_{i j k} { 0, 1} (i , j )

k k K , (i , j ) A²

t²_i 0 i i J

t^d_{r k} 0 k r r R, k K

t^a_{r k} 0 k r r R, k K

ur k l { 0, 1} k l

r r R, k K , l L

min

r R

frzr +

(i ,j ) A¹ l L

c¹_{i j}x¹_{i j l} +

(i ,j ) A²k K

c²_{i j}x²_{i j k} +

(o,j ) A¹ l L

f¹x¹_{oj l} +

r R j V²k K

f ²x²_{r j k}

f^e, e E

x¹_{i r l} zr i V¹, r R, l L

r R

x¹_{or l} 1 l L

x¹_{i r l}

(o,r ) A¹:r R

x¹_{or l} i V¹, l L

x¹_{j i l} = x¹_{i j l} i V¹, l L

x²_{r j k} zr r R, k K , j J

r R j J

x²_{r j k} 1 k K

i V²k K

x²_{i j k} = 1 j J

j J

x²_{r j k} =

j J

x²_{j r k} r R, k K

i V²

x²_{i j k} =

i V²

x²_{j i k} j J, k K

j J

t¹_ol T^{z er o} M (1

r R

x¹_{or l}) l L

t¹_{r l} t¹_{i l} + T_{i r}¹ M (1 x¹_{i r l}) l L , i V¹, r R

t^end_l t¹_{r l} + T_{r o}¹ M (1 x¹_{r ol}) l L , r R

t^{en d}_l T^{f i n}+ M (1

r R

x¹_{r ol}) l L

t¹_{r l} M

i V¹

x¹_{i r l} r R, l L

t^end_l M

r R

x¹_{r ol} l L

l L T^{z er o}

l L T^{f i n}

t²_j t^d_{r k}+ T_{r j}² M (1 x²_{r j k}) k K , r R, j J

t²_j t²_i + T_{i j}² M (1 x²_{i j k}) i , j J, k K

t^a_{r k} t²_i + T_{i r}² M (1 xi r k) k K , r R, i V²

t^d_{r k} M

i J

x²_{r i k} r R, k K

t^a_{r k} M

i J

x²_{r i k} r R, k K

t²_j aj j J

t²_j bj j J

r

k j

k r

t^d_{r k} t¹_{r l} M (1 ur k l) r R, k K , l L

t¹_{r l} t^a_{r k} M (1 u_{r k l}) r R, k K , l L

j J^P i V²

x²_{j i k} M

r R l L

ur k l k K

ur k l

i V¹

x¹_{i r l} r R, k K , l L

ur k l

j J^D

x²_{r j k} r R, k K , l L

ur k l

j J^P

x²_{j r k} r R, k K , l L

j J^D i V²

x¹_{j i k} M

r R l L

ur k l k K ;

zr { 0, 1} r R; ur k l { 0, 1} r R, k K , l L ; x¹_{i j l} { 0, 1} (i , j ) A¹, l L ; x²_{i j k} { 0, 1} (i , j ) A², k K ; t¹_{i l} 0 i V¹, l L ; t^end_l 0 l L ; t²_i 0 i J ; t^d_{r k}, t^a_{r k} 0 r R, k K .

l

k r r

k

R

Chapt er 3

T he solut ion approach

T he t wo-echelon locat ion-rout ing problem (2E-LRP ) is a difficult opt imizat ion problem because it combines t wo non-det erminist ic p olynomial-t ime (NP ) hard problems: facility locat ion and vehicle rout ing. At t acking such a hard problem head on is not feasible when t he inst ances reach a cert ain size. In fact , t he result s obt ained wit h commercial solvers show t hat only small inst ances are solved opt imally, and large inst ances are not even solved wit h a feasible solut ion . T herefore, a heur ist ic approach is required t o t ackle large-size real inst ances. In t his chapt er , we propose a decomposition-based heuristic for t he t ime- driven 2E-LRP wit h synchronizat ion and sequent ial delivery and pickup waves. T he solut ion approach decomposes t he original problem int o t hree main phases: choosing t he int ermediat e facility configur at ion , assigning cust omers t o t he int ermediat e facilit ies, and solving t he rout ing sub-problem .

In solut ion approaches for LRP s, t he choice of facilit y configurat ion has a considerable effect on t he solut ion qualit y because it changes t he vehicle rout es and dist ribut ion cost s.

Choosing t he facility configur at ion b ecomes more t echnically challenging when t here are a large number of p ot ent ial sit es for facilit ies and t he facilit y op ening cost s are considerably lower t han t he rout ing cost s. In heur ist ics for LRP s, a common approach is t o st art wit h an init ial facilit y configur at ion t hat is chosen eit her randomly or based on a crit erion ( e.g.,

i 2 i |R|

|R|

i 2 i |R|

CHAP T ER 3. T HE SOL UT I ON AP P ROACH

generat e a pool of feasible rout es for t he second echelon and solve t he rout ing sub-problem at t he second echelon using a set-part it ioning model. T he aim of t he set-part it ioning model is t o minimize t he rout ing and fixed usage cost s of vehicles at t he second echelon . T he set -part it ioning model provides t he best rout es from t he pool of feasible rout es and t he corresp onding rout ing and vehicle fixed cost s. W e define sub-iteration in t he algorit hm as t he number of it erat ions t hat t he pool of feasible rout es for t he second echelon is updat ed . In each sub-it erat ion , t he pool of feasible rout es is updat ed by t he generat ion of new rout es using neighb orhood search and t he set -part it ioning model is solved . T his is it erat ed for a given number of sub-it erat ions and we save t he solut ion wit h t he lowest value for rout ing and fixed usage cost s at t he second echelon . In t he next main it erat ion , we choose anot her RP configur at ion in t he RP plan and follow t he second and t hird phases of t he algorit hm . T he algorit hm st ops aft er all RP configur at ions in t he RP plan are examined and t he b est found solut ion (i.e., t he one t hat provides t he lowest value for sum of RP op ening cost s, rout ing cost s, and fixed vehicle cost s) is saved .

T he t hird phase of t he decomp osit ion-based heur ist ic is similar t o a column generat ion approach . In t he st andard column generat ion approach (Desaulniers et al ., 2006; Lubbecke and Desrosiers, 2005) , t he rout es (i.e., column s) are generat ed via a sub-problem (e.g., short est pat h problem , knapsack problem) . T hen, t he generat ed rout es are given t o t he mast er problem (i.e., set-part it ioning formulat ion) in order t o find t he best rout es. T his procedur e is it erat ed unt il a st op crit erion is met . Column generat ion approaches for t he LRP have b een used in previous lit erat ur e. Among t hem , t he papers by Akca et al. (2009) and Cont ardo et

al.

(2013) ar e wort h ment ioning. Cont ardo et al. (2013) formu lat ed t he LRP as a set -part it ioning problem and int roduced inequalit ies in order t o st rengt hen t he relaxed linear program . T he problem is solved by column generat ion , where t he mast er problem is a set -part it ioning formulat ion and t he sub-problem is a capacit at ed short est pat h problem . However , bot h approaches proposed by Akca et

al.

(2009) and Cont ardo et al. (2013) cannot solve large inst ances in a reasonable amount of comput at ional t ime.

P =

i R

Pi

Pi i

Sp Sp p Pi

Sp= 1 r p

f_r

p Pi r p

fr

+ 2 r p

AT_r

p Pi r p

ATr 3

r p r p

T_{r r}²

p Pi r p r p

T_{r r}² p Pi

ATr r

ATr = ^{j JP JD} T_{r j}²

|J^D| + |J^P| r R

T_{r j} ² r R j J

1, 2 3

p P_i Pi

p Pi

Pi

p Pi Pi

p Pi Sp

Pi

i P_i |P_i|

Sp

|Pi| =

|R|

1

|R|

i = 1

|R|

i

N 1 < i |R|

|P1| = |R| |P|R|| = 1

N |P_i| N 2^|R| .

|P_i^A| p / Pi

p P_i ^A i 2 i |R|

Pi P_i^A

P_i ^A |P_i^A| = |Pi| , 2 i |R|

0 1

J ORP

c²_{r j} r ORP j J

r j { 0, 1} j J

r ORP

J ORP

c²_{r j} r j

r j { 0, 1} j r

min

r O R P j J

c²_{r j} r j

r O R P

r j = 1 j J

j J

r j 1 r ORP

r j { 0, 1} r R, j J

r ORP

S s S

o, i1, . . . , in, j1, . . . , jm, o i1, . . . , in ORP D , j1, . . . , jm ORP P

o ORP D

S i ORP D ORP P

i ORP P j ORP D s S

j ORP D ORP P

s S T^{z er o} s S

T^{f i n} T^{z er o}

l¹_s T^{f i n} T^{z er o} s S

l_s ¹ s S

l¹_s =

i ,j s

T_{i j}¹ s S

T_{i j} ¹ i j

c¹_s s S

c¹_s =

i ,j s

c¹_{i j} s S

F_p¹(S) S

p

F_p¹(S) = f ¹n_s+

s S

c¹_s p P

ns S f ¹

s S

r ORP L_r L_r

Lr = min

s S{ Lr(s)} r ORP L_r(s)

r ORP s S

Lr(s) = (T^{f i n s}_{M (r )}T (M (r ), o)) (T^{z er o}+ ^s_rT (o, r )) s S, r ORP D , M (r ) ORP P

T (i , j ) i j

i , j O ORP D ORP P M (r ) r ORP D

ORP P ^s_i i s

s S, i ORP D ORP P

S K =

r O R P

Kr

Kr r ORP

k Kr r ORP

k K

r, . . . , i , j , . . . , r

j J^D J^P k K j J^D

i J^P k K l²_k k K

l² = T² k K

k K_r, r ORP k Kr, r ORP

r Lr

k K

T WD =

[e^D, l^D] T WP = [e^P, l^P]

e^D l^D

e^P l^P

e^P l^D

k K k K

r, i1, . . . , in, r i1, . . . , in J^D, r ORP

i1 in k K

r ORP l^D e^D

Tin l^D e^D

Tin in

k K