《物流系统分析与优化》课程教学课件（PPT讲稿）Trucking Scheduling in Container Terminals

Trucking Scheduling inContainer Terminals

Trucking Scheduling in Container Terminals

.Typicalactivities involved in a transportation job performed by a truck areasfollows:(i)whenatransportationjobisdispatchedtoanidletruck,ittravelsfromthecontainerdrop-offlocationofitslastjobtothecontainerpick-uplocationofthedispatchedjobandwaitsfora crane (quay/yardcrane)toserveit;(ii)afterbeingloadedwithacontainerbythecrane,thetruck travelsto the container drop-off location and waits fora crane(yard/quay crane)to unload the container; (ii)once thecontainerisunloaded,thetruckisavailabletoperformanothertransportationjob.Thetimetoprocessatransportationjobdependsonthetimetakenbythecranetoload a container onto andoffthe truck and thetime spent bythetrucktravellingfromthecontainerdrop-offlocationofitslastjobtothepick-uplocationofthenextjob.Hence,theprocessingtimeofajobdependsonthejobprocessing sequence of thetruck dispatchedtoit

• Typical activities involved in a transportation job performed by a truck are as follows: (i) when a transportation job is dispatched to an idle truck, it travels from the container drop-off location of its last job to the container pick-up location of the dispatched job and waits for a crane (quay/yard crane) to serve it; (ii) after being loaded with a container by the crane, the truck travels to the container drop-off location and waits for a crane (yard/quay crane) to unload the container; (iii) once the container is unloaded, the truck is available to perform another transportation job. The time to process a transportation job depends on the time taken by the crane to load a container onto and off the truck and the time spent by the truck travelling from the container drop-off location of its last job to the pick-up location of the next job. Hence, the processing time of a job depends on the job processing sequence of the truck dispatched to it

.Transportinga container fromits pick-up locationto its drop-offlocationisreferredto asajobforthetrucks.· An efficient truck operation can speed up container handlingprocesses, smooth containerflows, and thus improve terminalperformance..Schedulingafleetoftruckstoperforma setoftransportationjobswith sequence-dependent processing timesand different readytimesto minimize makespan is formulated as an integer program

• Transporting a container from its pick-up location to its drop-off location is referred to as a job for the trucks. • An efficient truck operation can speed up container handling processes, smooth container flows, and thus improve terminal performance. • Scheduling a fleet of trucks to perform a set of transportation jobs with sequence-dependent processing times and different ready times to minimize makespan is formulated as an integer program

NotationsM-thenumberofidenticaltruckswithunitcarryingcapacity.N-numberofcontainerstobetransportedbytheMtrucksinthecurrentperiod:Lm-Initiallocationoftruckm.rm-Initialavailabletime of truckmP,-Pickuplocationofjobi.D,-Dropofflocationofjobitr-Truck (loadedorempty)traveltimebetween locationl'e(LmP,D)and locationle(P,D)alongtheshortestpathThe travelling time between two locations is equal to the rectilinear distance between the two locations divided by the truck travelling speed..a-ReadytimeofjobiT,-Durationof jobi(fromthemomentthatthetruckdispatchedforjobiarrivesatP(pick-uplocationforjobi)tothemomentthatitstartstoleaveD,(thedrop-offlocationofjobi).).Processingtimeofjobi=truckstartsmovingfromitscurrentlocationtoP,+T.Theprocessingtimeofeachjobissequencedependent

Notations • M - the number of identical trucks with unit carrying capacity • N - number of containers to be transported by the M trucks in the current period • Lm – Initial location of truck m • rm – Initial available time of truck m • Pi – Pickup location of job i • Di – Dropoff location of job i • tl’l – Truck (loaded or empty) travel time between location l’{Lm Pi Di } and location l {Pi Di } along the shortest path • The travelling time between two locations is equal to the rectilinear distance between the two locations divided by the truck travelling speed. • ai – Ready time of job i • Ti – Duration of job i (from the moment that the truck dispatched for job i arrives at Pi (pick-up location for job i) to the moment that it starts to leave Di (the drop-off location of job i).) • Processing time of job i = truck starts moving from its current location to Pi + Ti • The processing time of each job is sequence dependent

Xiim a binaryvariable which takesavalue of 1 iftruck m (m=1,2,..,M)processes jobjj=1,2,...,N+)after jobi(i=1,2,...,N),wherejobN+1isadummyjobusedtofacilitatetherepresentation of the case when job i isthelast job processedbytruckm.Yima binaryvariablewhich takes a value of 1 if truck m (m =l,2,...,M)processes jobi(i =1, 2,..., N).Cithecompletiontimeofjobi(i=l2,...,N).Wthe makespan of the N jobs.DenotethesetofXiimbyX,thesetof YimbyY,and thesetof CbyC

MinimizeWsubjectto(1)Ci≤Wi=1,2....,NMZYm=1 i=1,2...N(2)m=1N+1Z(3)Xujm≤Yimi=1,2,...,Nj=landi+)ND(4)Xijm≤Yjmj=1,2,**.Ni=land i+j1≥Xijm+Xjm≥Yim+Yjm-1i,j=1,2,...,Nyandij;(5)m=12,.MJanditj;C+ID.P, +T≤K(I-Xijm)+Cji,j=1,2,...,N(6)m=1,2,...M(7)a+T≤Ci=1,2,.....N(8)rm+t..P+T≤Ci=1,2,...,N:m=1,2....,MXijmYime(0,1)i=0,1....,N-I;j=1,2....,N;m=1,2.....M(9)(10)Candw≥0j=l,2....,NwhereKisalargepositivenumber

Theobjectiveof thetruck scheduling problemistominimizethemakespan of theN jobs.Constraints(1)givethemakespan.Constraints(2)ensurethateach jobis processedby onlyonetruck.Constraints(3)-(5)givetherelationshipbetweenXandYforjobsprocessedbythe sametruck.Constraints(3)ensurethat Yim=1 if truck m processes a job after job iConstraints(4)ensurethatYim=1if truckm processes a jobbefore jobi.Constraints(5)ensure that if Yim+Yim=2,truck m processes either jobibefore job jor jobjbeforejobi.Constraints(6)givetherelationshipbetweenthecompletiontimeof a jobandthatofitssuccessor.Constraints(7)statetherelationshipbetweenthecompletiontime,readytime,andduration of a job.Constraints (8)give therelationship between the duration and completiontime of a job,the truck readytime, and the travel time of a truck from its initial location tothepick-up location.Constraints(9)and (10)are simpleconstraints which definetherangeofvaluesforX,Y.CandW

. The truck scheduling problem is equivalent to the problem ofscheduling M identical machines (trucks)tohandle Nnon-preemptive jobs withsequence-dependent processing times anddifferent ready times to minimize makespan

• The truck scheduling problem is equivalent to the problem of scheduling M identical machines (trucks) to handle N non-pre￾emptive jobs with sequence-dependent processing times and different ready times to minimize makespan

GA·Solutionrepresentation:Atwo-partchromosomestructurewithtotallengthN+M: 3-truck, 9-job example927K3Truck 2Truck 3Truck1Figure 1.An example schedule encoded in two-part chromosome structure

GA • Solution representation • A two-part chromosome structure with total length N+M • 3-truck, 9-job example

.Initialization:50%randomgeneration+50%generatedbyagreedyheuristic:ThegreedyheuristicfirstpartitionsthesetofNjobsintoMsubsets.Eachsubsetrepresentsagroupofdesirablejobsforaparticulartruck.Inpartitioningtheset,theheuristictriestobalancethenumberof jobsin eachsubset

• Initialization • 50% random generation + 50% generated by a greedy heuristic • The greedy heuristic first partitions the set of N jobs into M subsets. Each subset represents a group of desirable jobs for a particular truck. In partitioning the set, the heuristic tries to balance the number of jobs in each subset