Two-Echelon Multi-Trip Multi-Traffic Pickup and Delivery Problem with Time Windows and Synchronization

Nội dung text: Two-Echelon Multi-Trip Multi-Traffic Pickup and Delivery Problem with Time Windows and Synchronization

1. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 Two-Echelon Multi-Trip Multi-Traffic Pickup and Delivery Problem with Time Windows and Synchronization Quang Ngoc Nguyen*, Nghia Nguyen Duc, Phuong Khanh Nguyen Hanoi University of Science and Technology, Hanoi, Viet Nam *Email: quangnn@etc.vn Abstract In City Logistics context, multi-echelon distribution system normally supports multi-traffic: inbound, outbound, and intra-city traffic. Tackling multi-echelon model with multi-traffic simultaneously will take benefit from saving time and money. Therefore, we study a new problem class, the Two-Echelon Multi-Trip Multi-Traffic Pickup and Delivery Problem with Time Windows and Synchronization. We consider the synchronization process of transshipment at satellites between vehicles with the temporary storage mechanism. As the proposed problem consists of two echelons with two separate fleets of vehicles, we thus propose the bottom-up approach to solve the problem. The experiment is to study the proposed model and analyze the satellite synchronization. Keywords: Two-Echelon, MTT-PDTWS, ALNS 1. Introduction*and Literature Review freighter operating on the second echelon within the city. Second, the e2c and c2e demands are City Logistics (CL) literature and projects often synchronized at satellites by not only exchanging address inbound movements only, reflecting the them directly from the vehicles as in the MTT- dominant position of the traffic proceeding from the PDTWS but also using temporary storage to store exterior of the city towards its center. Yet, the them for later transshipment in case the vehicles volumes of freight produced within the city and arrive late at satellites. It thus helps to reduce empty shipped to locations outside it may be significant. vehicles on the road but makes the problem harder to Tackling multi-echelon model with multi-traffic tackle. Third, we include the capacity of each satellite simultaneously will therefore take benefit on saving as a new constraint for the problem. time and money. Consequently, addressing the needs of these all different types of transportation demands The decomposition approach is proposed to in a multi-echelon freight distribution system may handle the problem. Experimental results show the greatly contribute to achieving the CL mobility, solution quality and examine the satellite environmental, and quality-of-life objectives. synchronization. To our best knowledge, Crainic et al. was the The remainder is organized as follows. Section 2 first to introduce the Multi-Trip Multi-Traffic Pickup contains the problem description. The proposed and Delivery Problem with Time Windows and methodology is described in Section 3. Computation Synchronization (MTT-PDTWS) addressing all three results are then reported and analyzed in Section 4, types of traffic: the inbound movement (external-to- while conclusions are considered in Section 5. customer demands, e2c), outbound movement 2. Problem Setting (customer-to-external demands, c2e), and internal movement within the city (customer-to-customer, In the 2E-MTT-PDTWS setting, two-echelon c2c) [1]. In this paper, we aim to extend the MTT- system consists of two homogeneous fleets of PDTWS by introducing a new problem, the Two- vehicles operating on each echelon to transport Echelon Multi-Trip Multi-Traffic Pickup and freight (1) between the central distribution center Delivery Problem with Time Windows and (CDC) located on the outskirts of the city and a set of Synchronization (2E-MTT-PDTWS). The extensions customers C within the city through a set of satellite are three folds. First, the distribution system is two- facilities S , and (2) between customers of set C . No echelon, thus requiring the need of using two direct shipping between the CDC and customers is different sizes of vehicles: the bigger size, fleet of allowed. Each satellite sS∈ has a no-wait, hard urban-trucks transporting freight on the first echelon opening time window ts()()−η, ts specifying the outside the city; and the smaller size, fleet of city-  earliest and latest times a vehicle may arrive at , respectively. Each customer may request different ISSN: 2734-9373 services at different periods of time: 1) receive e2c demands from different satellites, possibly within Received: 12 May 2019; accepted: 22 December 2020 different time windows; 2) ask for c2e demands to be 25
2. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 picked up and transported to one of a given subset of loads e2c demands from a satellite to deliver them to satellites; 3) specific pairs of customers may ship c2c customers inside the city, generating a route called a demands between them. We model the time 2nd-level delivery leg; (2) picks up c2e demands from dependency by identifying each above particular the customers to bring them to a satellite, creating a demand as customer demand and thus define: respective a 2nd-level pickup leg; and (3) transfers c2c D demands between customers within the city, making a - The set of delivery-customer demands, dC∈ , 2nd-level c2c leg. Each c2c leg must follow the last- each being characterized by the wish-list of satellites in-first-out (LIFO) policy to ensure that no handling SSd ∈ where customer wants to receive, and the is required while unloading freight from the vehicle. time window when the delivery must be performed, Thus, each city-freighter departs at the garage g to the choice of a particular satellite being part of the perform one or several 2nd-level delivery and/or decisions characterizing the problem; pickup and/or c2c legs, and returns g to finish its P activity. Such sequence performed by each city- - The set of pickup-customer demands, pC∈ , freighter is called a 2nd-level work assignment. each characterized by the customer shipping it, the time window within which the pickup must be Vehicles operate according to the Pseudo- performed, as well as by the set of admissible Backhaul strategy in which any leg must be completed before another one may start, i.e., vehicles satellites SS∈ to which the demand may be p need to be empty when finishing a leg [2]. delivered, the choice of a particular one also being part of the problem decisions; In general, the activity of a vehicle at a satellite is “unload only”, “load only” or “unload and load”. ∈ - The set ( pd , ) R of c2c-customer-demands, Fig.2 and Fig.3 represent these activities for the each request requiring a demand to be transported urban-truck and the city-freighter respectively. from a c2c-pickup-customer-demand pC∈ P to a Striped and empty disks stand for pickup and delivery cc2 customer demands, respectively, dashed lines indicate ∈ D c2c-delivery-customer demand dC cc2 . empty moves. δ Let (iq,,i( i) ,[ e ii , l]) stand for the quantity Fig.2a and Fig.2b depict instances of the “load only” operation in which, after arriving at satellite s, qqq>=−0( for pd , ∈ R need to be delivered ipd ( ) the urban-truck loads c2e demands, then it leaves s or picked up at the customer demand for its next satellite to continue loading additional c2e PDP D demands or to go to the CDC to end its activity. The iC∈{ ∪∪ C Ccc22 ∪ C cc} within its hard time two instances differ in the status of urban-truck window [elii, ] , with a service time δ (i) . arrival at the satellite only. The urban-truck arrives empty at s in Fig.2a, while with c2e demands in Freights in the 2E-MTT-PDTWS is thus Fig.2b. Fig.2c and Fig.2d represent instances of the transferred as follows: “unload only” activity when the urban-truck arrives at s with e2c demands. At satellite s, if it unloads all - A fleet of urban-truck K1 with capacity Q1 and a freights, Fig.2c, it then leaves s empty. Otherwise, it fixed cost F1 is operated within the first echelon. unloads part of its e2c demands, Fig.2d, then leaves s Each urban-truck might do either one or both ’ following activities: (1) leave the CDC with e2c for its next satellite s to continue unloading its e2c demands, it then delivers freight to a subset of demands. Fig.2e depicts the “unload and load” case in satellites. Once empty, the vehicle may either return which, after unloading all e2c demands, the urban- truck starts to load c2e demands at the same satellite to the CDC to complete its task or traveling to s, and leaves s to either bring the freight back to the satellites to load c2e demands and then bringing it back to the CDC; Thus, the urban-truck performs CDC or to go to the next satellite for a “load only” only one 1st-level delivery leg in the former case (see activity. Fig.1a), while a 1st-level delivery leg and then a 1st- Fig. 3a depicts the “unload only” case of a city- level pickup leg in the latter (see Fig.1b) (The dashed freighter in which, after arriving at the satellite s with lines stand for an empty move); (2) leave the CDC the collected c2e demands, the city-freighter unloads empty, it then travels to satellites to collect c2e all freight, then it leaves s empty. Fig.3b represents demands and then returns to the CDC; In this case, the “load only” case when the city-freighter arrives the urban-truck operates only one 1st-level pickup leg empty at s and loads e2c demands, it then delivers it (see Fig.1c). Each such sequence is called a 1st-level to designated delivery customer demands. Fig.3c work assignment. depicts instance of “unload and load” operation in which, after unloading all c2e demands collected - A fleet of city-freighters K with capacity Q2 and 2 from pickup-customer demands, the vehicle loads e2c a fixed cost F2 is operated within the second echelon. demands and leaves to travel to delivery-customer Each city-freighter performs following activities: (1) demands to deliver it. 26
3. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 Fig. 1. The 1st-level work assignment illustration Fig. 2. Activities of an urban-truck at the satellite urban-trucks is performed. The temporary storage at the satellite is thus taken into account in case vehicles could not arrive concurrently for transshipment. Fig.4 gives an illustration of this necessary. Lines stand for the freight flow between vehicles. Fig. 3. Activities of a city-freighter at the satellite Let TTUL, be the times required, respectively to unload and load an urban-truck at a satellite. Similar '' times, TTUL, , are assumed for a city-freighter. For simplicity, we assume that these time durations are equal at all satellites and independent on the transferred quantity. 2.1. The Temporary Storage and Synchronization at Satellites At satellites, the e2c demand is transferred from Fig. 4. An example of waiting cycle caused by the urban-trucks to appropriate city-freighters, while the absence of the temporary storage transshipment of c2e demand from city-freighters into 27
4. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 Two urban-trucks {1, 2} and two city-freighters the vehicle k arrives at s at time t. The vehicle k starts {1’, 2’} all perform the “unload and load” activity at unloading from time t, thus finishes unloading at the the same satellite. At the first echelon, urban-truck 1 time tT+ U . If the city-freighter k′ is ready to load at unloads its e2c demands {dd, } and then loads c2e 12 the time tT+ U , freight is transferred directly to this demands {pp34, } of city-freighter 2’, while urban- vehicle, the city-freighter k′ then leaves s at the time tT++ T' once it finishes loading. Otherwise, freight truck 2 unloads e2c demands {dd34, } and loads c2e UL is placed in the temporary storage; demands {pp12, } from city-freighter 1’. At the second echelon, city-freighter 1’ unloads its c2e - (1-m) case: A single urban-truck k transfers freight to m city-freighters kk'',, : We assume the demands {pp12, } and loads e2c demands {dd12, } of 1 m urban-truck 1, while city-freighter 2’ unloads arrival time of the urban-truck k is t. The urban-truck k thus performs unloading at time t for a duration TU . { pp34, } and loads {dd34, } of urban-truck 2. In this The appropriate freight transferring between each pair case, the absence of the temporary storage makes ' = these four vehicles trapped into a waiting cycle, i.e., of vehicles (,kk1 ) where im1, , is considered each unloading vehicle must wait for the appropriate separately as a representation of the previous case loading vehicle to be empty in order to transfer its (1-1); freight (urban-truck 1 waits for city-freighter 1’, city- - (n-1) case: n urban-trucks kk,, transfer freighter 1’ waits for urban-truck 2, urban-truck 2 1 n waits for city-freighter 2’, city-freighter 2’ waits for freight to a single city-freighter k′ : We assume urban-truck 1) while none of these vehicles could be urban-trucks kk1,, n arrive at s at times urban- emptied without using the temporary storage. One trucks tt1,, n , respectively. Urban-trucks kk1,, n could make a vehicle empty by placing its freight in start unloading respectively from times tt,, , for a the temporary storage, the waiting cycle is therefore 1 n broken. duration TU . If all urban-trucks arrive at s simultaneously, then freight is either transferred Let Q be the maximum temporary storage s directly to city-freighter k′ if city-freighter k′ is ∈ capacity of the satellite sS. The unloading (resp. ready to load at time tT+ , or placed in the loading) time at the temporary storage is assumed to 1 U ′ be zero. Freights transfer between vehicles through temporary storage if city-freighter k is not ready. satellites is assumed to follow the operational Otherwise, in the case these urban-trucks do not characteristics given as below: arrive simultaneously, the freight that arrived previously is placed in the temporary storage; - No pre-emption: The unloading or loading of a vehicle cannot be interrupted; - (n-m) case: n urban-trucks kk1,, n transfer '' - As temporary storage is allowed, freight can be freight to m city-freighters kk1,,m : Depending on unloaded from a vehicle before the appropriate the transshipment performed, one could consider this receiving vehicles are available; case as a combination of any two or all three previous cases. For example, the transshipment in which - The unloading operation of a vehicle must be urban-trucks kk,, transfer freight to a single initiated as soon as it arrives at the satellite; 11n− city-freighter k ' while a single urban-truck k - The arrival time of a vehicle must be in the hard 1 n '' opening time window of the satellite; transfers freight to city-freighters kk2 ,,m could be considered as a combination of (n-1) and (1-m) cases. - The loading operation of a vehicle can start only after its unloading operation is completed (if any) and Given an illustrative example for the case (n-1) all freight to be loaded on is ready. Otherwise, the in Fig.5, we consider a satellite s, two urban-trucks freight that arrived previously is placed in temporary {1, 2} and one city-freighter {1′} . Urban-truck 1 storage. arrives at s at time t1 to unload e2c demands We below only provide the synchronization {dd,,, d} , while the arrival time of urban-truck process of transshipment in the direction from city- 12 5 freighters to urban-trucks. The reverse direction 2 is t2 and it unloads e2c demands {dd67,,, d 9} , would be similar. The synchronization is thus detailed the city-freighter 1′ is empty at time t′ and it loads based on the category of transshipment at a satellite s {dd, } of urban-truck 1 and {dd, } of urban-truck as follows: 12 67 2. Since the arrival times t and t play a symmetric - (1-1) case: The transshipment is performed from 1 2 role in this example, four possibilities of the an urban-truck k to a city-freighter k′ : We assume consolidation process are following: 28
5. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 = +≥′ - tt12 and tT1 U t: Urban-truck 1 and urban- from time tT1 + U , while {dddd6789,,,} of urban- truck 2 start to unload their demands at time t . After 1 truck 2 are also placed from time tT2 + U . Once arrive unloading for a time TU , they leave the satellite. At at time t′ , city-freighter 1′ starts loading demands + ′ this moment (i.e., tT1 U ), as city-freighter 1 is {dddd1267,,,} from the storage. Then, city-freighter already empty, demands dddd,,, are ' { 1267} 1′ leaves the satellite at time tT′ + L , and there are transferred directly to city-freighter 1′ without using only {ddddd34589,,,,} in the storage from this time. temporary storage, the remaining demands ∈ {ddd345,,} of urban-truck 1 and demands {dd89, } of The capacity of each satellite sS is measured urban-truck 2 are placed in the temporary storage. in the maximum number of urban-trucks (πs) and city- π ' city-freighter 1′ leaves the satellite at time freighters ( s ) that it can accommodate ' simultaneously. Let W be the set of waiting stations. tT1 ++UL T once it finishes loading; The vehicle cannot go directly to a satellite sS∈ , but - tt12= and tT1 +<U t′ : As the previous case, has to wait at a waiting station wW∈ instead, if urban-truck 1 and urban-truck 2 both finish unloading either its arrival time at s is before the opening time at time tT+ . At this moment, city-freighter 1′ has 1 U ts( ) −η, ts( ) , or there is no capacity available at not arrived yet, all demands {dd12,,, d 9} are s . therefore placed in the temporary storage. Once arrive, city-freighter 1′ performs loading from t′ for ' a duration TL , i.e., demands {dddd1267,,,} are transferred from the temporary storage to this vehicle. Thus, from time t′ , there are only {ddddd34589,,,,} in the temporary storage; - tt12< and tT2 +≥U t′ : Urban-truck 1 and urban- truck 2 perform unloading respectively at times t1 ′ and t2 , for a duration TU . In fact, city-freighter 1 is Fig. 5. An example of activities of vehicles from both echelons at the satellite s ready to load at time tT2 + U (i.e., when urban-truck 1 and urban-truck 2 both finish unloading). However, 2.2. Problem Definition demands {dd, } of urban-truck 1 and {dd, } of 12 67 An example of the solution to the problem is urban-truck 2 do not arrive at the satellite represented in Fig.6 which models a partial solution simultaneously. Therefore, the demand of urban-truck with four work assignments performed by two urban- 1 that arrived previously is placed in temporary trucks {1, 2} on the first echelon and two city- storage. At time tT2 + U , city-freighter 1′ performs freighters {1’, 2’} on the second echelon. Dashed loading, i.e., demands {dd, } of urban-truck 2 are lines stand for the empty travel. The urban-truck 67 number 1 performs a 1st-level work assignment that transferred directly from urban-truck 2 to it, while consists of a sequence of two legs {rr12, } where {dd12, } of urban-truck 1 are moved from the r= CDC, s, s is a 1st-level delivery leg and temporary storage and loaded onto it. At the same 1 { 12} st time, the remaining demands of urban-truck 2 r 2 = { s 23,, s CDC} is a 1 -level pickup leg. In details, (i.e.,{dd89, } ) is placed in the temporary storage. it first leaves the CDC to deliver e2c demands to s1 , City-freighter 1′ leaves the satellite at time s2 . At the satellite s2 , after finishing unloading to ' tTT2 ++UL once all freight is loaded, and there are complete leg r1 , the urban-truck number 1 becomes only {ddddd,,,,} in the temporary storage from 34589 empty. It then starts to perform leg r2 by loading c2e this time; demands at s2 , then s3 , and finally brings them back - tt12< and tT2 +<U t′ : As in the previous case, to the CDC. Similarity, the urban-truck number 2 st = Urban-truck 1 and urban-truck 2 finish unloading performs a 1 -level delivery leg r3 { CDC , s4 } and st = respectively at times tT1 + U and tT2 + U . As city- then a 1 -level pickup leg r4 { s4 , CDC }. On the freighter 1′ is not available at satellite when they both second echelon, the city-freighter 1’ performs a '''' finish unloading, all demands {dd12,,, d 5} of sequence of four legs {rrrr1234,,,} where urban-truck 1 are placed in the temporary storage ' ' nd r1= { sdd 156,,} and r3 = { sdd478,,} are 2 -level 29
6. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 ' nd capacities of temporary storage, satellites, vehicles, delivery legs, r2 = { pps6, 73 ,} is a 2 -level pickup ' nd and time-related constraints are satisfied. leg, and r4 = { pd55,,,} pd 66 is a 2 -level c2c leg. More precisely, it starts empty from the garage g to ' perform delivery of leg r1 : load e2c demands at s1 and delivery them to delivery-customer demands ' dd56, . It is now empty, so it continues to do leg r2 : go to pickup-customer demands pp67, to load c2e demands and bring them to satellite s3 to unload ' there. After finishing leg r3 , it services two requests ( pd55,,,) ( pd 66) in the LIFO order pd55,,, pd 66 before moving empty back to garage g. City-freighter 2’ performs six legs sequentially rrrrrr'''''',,,,, , { 5678910} ' = ' = where r6{ pps 1,, 22} and r9{ pp 3,,, 4 ps 54} are Fig. 6. An example of the solution nd ' = 2 -level pickup legs, r7{ sdd 212,,} and 3. Solution Method ' = nd r10 { sdd434,,} are 2 -level delivery legs, 3.1. General Structure ' = { } and r' = pd,,, pd are 2nd- r5 ppdd1,,, 221 8{ 33 44} For simplification, we only allow the search to level c2c legs. One could see that once loading p5 is explore feasible solutions. First, an initial feasible finished, city-freighter 2’ has to move to the waiting solution z is generated using a greedy method station w and wait there in order to reach s in time seeking to fully utilize vehicles and minimize the 1 4 total cost. The solution z is then assigned as the for synchronization. current best solution zbest . As the 2E-MTT-PDTWS The 2E-MTT-PDTWS is defined on a directed consists of two echelons with two separate fleets of graph G= ( VA, ) , which represents the two-echelon vehicles, we divide the solution to the problem into two parts: the first part is the schedule of the urban- system. The first echelon is defined by G= ( VA, ) 1 11 trucks on the first echelon, while the second part is with V1 ={ CDC} ∪∪ S W and the schedule of the city-freighters on the second echelon. We thus use the bottom-up approach to solve A= i, j | i ∈ V \ W , j ∈∪ V }{, ws | w ∈ W , s ∈ S 1{( ) 11( ) } the problem. Consequently, there are two steps that need to be performed at each iteration of the The second echelon is defined by G2= ( VA 22, ) with algorithm. In the first step, to schedule the city- = ∪∪ ∪PDP ∪ ∪ ∪ D V2{ g} SWC C Ccc22 C cc and freighters we rebuild the second part of the current PP solution z by inheriting the adaptive large A2 = { ( gi, ) | i∈∪ S C ∪ Ccc2 } ∪ PP neighborhood search (ALNS) introduced in [3]. {(iji,|) ∈ C , j ∈ C ∪∪ S W} ∪ Given this schedule together with synchronization (iji,|) ∈ CD , j ∈ C PP ∪ C ∪ C D ∪∪ S W ∪ constraints at satellites, we then propose a heuristic { cc2 } algorithm, named QFE, to regenerate the first part of P PD {(iji,|) ∈ Ccc2 , j ∈ C cc 22 ∪ C cc ∪∪ S W} ∪ the current solution z in the second step. We then . update the zbest if the solution z obtained after two (ijiCjCCCSW,|) ∈D , ∈ PDP ∪ ∪ ∪∪ ∪ { cc2 cc 22 cc } steps is better than it. The overall number of iterations PDP is IT . The structure of the proposed algorithm for {(iji,|) ∈ Sj , ∈∪∪ C C Ccc2 ∪∪ W} max DD the 2E-MTT-PDTWS is given in Algorithm 1. {(ig,) | i∈ C ∪ Ccc2 ∪∪ S} {,|( ws) w ∈ W , s ∈ S } Algorithm 1 The proposed algorithm Each arc (ij, )∈∪ A12 A is associated with a travel 1: Generate an initial feasible solution z ; cost cij and a travel time tij . Thus, the 2E-MTT- 2: zz← ; PDTWS can then be seen as the problem of (1) best assigning pickup-customer and delivery-customer 3: Initialize weights for destroy and repair demands to satellites, and (2) finding efficient work neighborhoods (all equal to 1); assignments operated at each echelon. The objective 4: repeat is to minimize the total cost, which is comprised of 5: Probabiliscally select a detroy and a repair the routing cost of operating the work assignments based on their current weights; and the fixed cost of using the vehicles, while 6: Apply the selected destroy and repair 30
7. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 neighborhood to the second part of z to obtain ( pC∈ P ), we know the satellite and the time t d ( t p ) the new solution z '' ; at which it needs to be loaded to a city freighter 7: if z" satisfies the acceptance criterion then (urban-truck). Accordingly, we need to schedule 8: Apply the heuristic alogrithm QFE to urban-trucks to (1): bring each e2c delivery-customer z '' to obtain the new solution z ' ; demand dC∈ D from the CDC to its appropriate 9: zz← ' ; satellite so that it could be loaded to the city d 10: if z ' is better than zbest then freighters at time t , and (2): go to appropriate satellite to start loading each c2e pickup-customer 11: zzbest ← ' ; P p 12: end if demand pC∈ at the time t and bring them back 13: end if to the CDC. 14: Adjust weights for all destroy and repair First, we sort all e2c delivery-customer demands neighborhoods; dC∈ D in ascending order of the time t d and store 15: until number of iterations ITmax has passed; D them in the set Cunserved . Initially, these e2c demands 16: return zbest ; D in Cunserved are not serviced by any urban-truck yet. 3.2. Initialize Solution We determine the satellite s1 having the demand D d1 An initial solution is created using the dC1 ∈ unserved with the earliest t , then schedule an decomposition approach by scheduling the fleet of urban-truck k to do an itinerary from the CDC to vehicles at each echelon. To schedule the fleet of city- s1 to service (transfer) the demand d1 directly. In freighters, we inherit the process of initiating the addition, for each demand d ' among e2c demands of solution in [3]. This process consists of two steps. At D P the first step, each pickup-customer demand pC∈ satellite s1 in Cunserved , we add d ' to this itinerary if ′ are first assigned to a satellite s selected from S . this vehicle could also service (transfer) d either p directly or through temporary storage without The selection is aimed to not only reduce the required violation of capacity Q . Once finish, we get all e2c travel distance of vehicles but also balance the total 1 delivery and pickup demand of each satellite, thus demands such that the urban-truck k need to deliver reduce the empty movements. A greedy algorithm is to satellite s1. We then delete these demands from then applied on the second step to build each work D Cunserved and find the next satellite s2 having the assignment sequentially until all customer demands ∈ D d2 are serviced. At each iteration of this greedy demand dC2 unserved with the earliest t so that algorithm, a suitable leg with the smallest average urban-truck can go from s1 to s2 to service this cost per unit demand will be concatenated to the demand directly without violation of capacity Q1 . current work assignment. Repeat the above process we get a 1st-level delivery Once we get the schedule of city-freighters, we leg that consists a sequence of satellites that urban- then use this information to schedule the fleet of truck k need to go through and quantity of e2c urban-trucks by applying our proposed QFE heuristic demands to deliver at each of these satellites. The algorithm. process is terminated once there does not exist any 3.3. The ALNS for the Second Echelon satellite with unserved e2c demands for urban-truck k to go to without violation of time and capacity. As In order to schedule vehicles of the second a result, we get a 1st-level delivery leg performed by echelon, we inherit the proposed ALNS proposed: for the vehicle urban-truck k . Therefore, we then try to destroy operators, we use random and worst cost schedule this vehicle to perform a 1st-level pickup leg destroy (customer level), worst utilization and time so that this vehicle will go back to the CDC with c2e related destroy (leg level); for the repair operator, we demands rather than empty. The process to create 1st- use the random greedy [3]. Destroy and repair level pickup leg for urban-truck k could also be done operators are selected probabilistically based on as what we have just done to create 1st-level delivery historical weights. To keep the diversification, the leg, but with c2e pickup-customer demands instead. worse solutions are accepted with a probability given by the Boltzmann factor. One could see that each 1st-level work assignment must has one of the three following 3.4. The QFE Heuristic Algorithm for the First forms: (1) a single 1st-level pickup leg; (2) a single Echelon 1st-level delivery leg; (3) a 1st-level delivery leg Once the ALNS is terminated, we obtain followed by a 1st-level pickup leg. Our QFE heuristic schedule of the city-freighters. As a result, for each thus aims to create the latest form as many as possible e2c delivery- (c2e pickup-) customer demand dC∈ D to reduce the number of urban-trucks. 31
8. JST: Smart Systems and Devices Volume 31, Issue 1, May 2021, 025-032 4. Computational Results are not allowed at satellites. For the remaining 66.85% of the cases without using temporary The objective of the numerical experimentation storages, at each satellite, every single urban-truck is to study the proposed model and analyze the transfers freight directly to four city-freighters, while satellite synchronization. The proposed algorithm is every single city-freighter does direct transshipment implemented in C++. Experiments are run on a 2.4 with three urban-trucks. GHz Intel i7 processor with 16GB of RAM. Table 2. Performance of the proposed algorithm 4.1. Instance Generation Average Test Average We inherit instance generation proposed by IT running time max set best cost Cranic et al. [1]. The CDC, supply points, waiting (min.) stations, and customers are uniformly distributed in a C1 22,487.95 6.95 square condinating in the interval [0,100]. Each city- 100,000 C2 24,433.64 9.26 freighter has the fixed cost (F2 = 500) , capacity C 34,784.23 19.85 (Q = 100) , unloading time T ' = 30 , and loading 3 2 ( U ) Avg. 27,235.27 12.02 ' time (TL = 30) . Each urban-truck then has C1 19,769.70 10.73 '' C2 23,501.81 11 { F1, QT 1, UL, T }= {2* F2 ,2.5* Q2 ,3* TUL ,3* T }, 200,000 respectively. The number of satellites and waiting C3 32,851.82 22.64 stations in each instance are all four. Each satellite Avg. 25,374.44 14.79 ' ' has capacity (π = 5 and π = 10 ) and maximum C1 18,930.78 76.33 s s temporary storage capacity Qs = 1,000 . The instance 500,000 C2 21,266.02 65.23 set consists of three sets CCC123,, with five instances C3 28,382.08 89.19 each. The number of customer demands for three sets Avg. 22,859.63 76.92 are 594, 761, 1070, respectively. Each customer 5. Conclusion demand has service time δ (i) = 20 and volume of We addressed a new problem class that applied demand q generated randomly in the range [5, 25]. i the two-echelon distribution system to the MTT- The characteristics of these instances are summarized PDTWS problem described in [3]. We consider the in the Table 1. synchronization process of transshipment at Table 1. Characteristics of the instances satellites between vehicles with the temporary storage mechanism. We proposed a decomposition D P Test set S W C C R method for the problem. At each step of the proposed algorithm, routing of the fleet of city- 400 44 150 C1 4 4 freighters is determined by the algorithm ALNS. 400 171 190 Latter, the QFE heuristic algorithm is applied to C2 4 4 obtain the schedule of urban-trucks. Experiments C 400 400 270 3 4 4 were run with the proposed instance datasets to 4.2. Computational Results study the problem and the satellite synchronization. Table 2 displays the average of the best cost and References the average running time obtained over 10 runs for [1]. T. Crainic, P. Nguyen, and M. Toulouse; Synchronized Multi-trip Multi-traffic Pickup & each ITmax within {100,000;200,000;500,000} . We Delivery in City Logistics; Transportation Research have observed that executing the algorithm with Procedia tenth International Conference on City 500,000 iterations yields an average improvement of Logistics; Spain; 2015; 26-39. the best solution of 9.9%, while requiring about 420% more time, when compared to the case of 200,000 iterations. It indicates that 200,000 iterations is the [2]. T. G. Crainic, F. Errico, W. Rei, and N. Ricciardi, Integrating c2e and c2c Traffic into City Logistics most appropriate value setting for ITmax . Planning, Procedia - Social and Behavioral Sciences, 39, 0, (2012) 47-60. We next examine the synchronization at satellites. On average, there is almost 33.15% of the cases, temporary storages at satellites need to be used [3]. Nguyen, Quang Ngoc and Duc, Nghia Nguyen and as the freight could not be transferred directly Nguyen, Phuong Khanh; Proceedings of the Eighth between vehicles. It thus helps to reduce the number International Symposium on Information and Communication Technology; SoICT 2017; Viet of vehicles running empty to satellites just for Nam; 2017; 439-446. transshipment on time in the case temporary storages 32