# The Linehaul-Feeder Vehicle Routing Problem with Virtual Depots and Time Windows

Authors: Huey-Kuo Chen; Huey-Wen Chou; Chia-Yuan Hsu
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

This paper addresses the linehaul-feeder vehicle routing problem with virtual depots and time windows (LFVRPTW). Small and large vehicles deliver services to customers within time constraints; small vehiclesen route may reload commodities from either the physical depot or from the larger vehicle at a virtual depot before continuing onward. A two-stage solution heuristic involving Tabu search is proposed to solve this problem. The test results show that the LFVRPTW performs better than the vehicle routing problem with time windows in terms of both objective value and the number of small vehicles dispatched.


---

## Body

## 1. Introduction

City logistics, which aims to reduce the nuisances associated with freight transportation in urban areas while supporting their economic and social development, has been a hot research topic over the last two decades. Logistics companies around the world have increased their competitiveness and experienced fast growth by adapting mathematical modeling techniques for optimizing vehicle routes. The existing scenarios that logistics companies may face vary, and new scenarios continue to arise. As a result, both researchers and practitioners are striving to find the best way to tackle different scenarios.Motivated by high land prices and narrow roads, new kinds of delivery services have been observed. The Black Cat-Takkyubin, a logistics company in Taiwan, dispatches a large vehicle to deliver commodities to its chosen customers, who are those with wide access roads and sufficient parking spaces. For customers who cannot be easily accessed by large vehicles due to inaccessible roads or lack of parking, delivery service is provided by smaller vehicles, that is, bicycles or motorcycles. The driver of the small vehicle can be the same driver as for the large vehicle or a different person. In the former case, the driver changes the transportation mode only at certain linehaul-feeder locations and then switches back. At linehaul-feeder locations, the large vehicle parks in a legal space, and then the parked small vehicle is used to continue delivery. Using this method, every customer can receive door-to-door service. Applying a similar delivery method, DHL simultaneously dispatches both large and small vehicles from the physical depot (PD) for commodity delivery. The small vehicles, when their commodity load is empty, visit the larger vehicle for reloading.In the US, a related delivery operation can also be observed through mail delivery. A postman is usually assigned to an area where he or she drives along a prespecified route, making several stops. At each stop, the driver exits the truck and delivers the mail by walking. When delivery is complete, the driver goes back to the main postal office.Common attributes of the aforementioned practices are that two types of transportation modes (i.e., large and small) are used for servicing two types of customers (i.e., type-I and type-II). The classification of customers is based mainly on parking conditions and large vehicle accessibility. Type-I customers can be serviced by both large and small vehicles, whereas type-II customers can only be serviced by small vehicles. Small vehicles, which have load capacity limitations, can reload from large vehicles, which stay at “virtual depots” (VDs). The VD is different from the PD in that it is not privately owned, but can be used by both large and small vehicles at low or no cost. This feature reduces the number of side trips to and from the PD for reloading and can result in meaningful cost savings.From the entrepreneur’s point of view, the PD is certainly more controllable than a VD. However, due to high land prices, it is difficult for logistics companies to increase the number of PDs. Thus, the VD becomes important for improving the efficiency of delivery operations. If the number of VDs and their locations are fixed, the delivery operation will usually be less efficient. In many situations, VDs are different on each day, depending on the business received. Therefore, it is reasonable to treat VDs as variables, rather than accommodating the rigid assumption of fixed VDs. This treatment implies that, if a type-I customer is serviced by the large vehicle, it will also act as a VD; otherwise, it can be serviced by either a small vehicle or the large vehicle depending on the insertion cost. In addition, time constraints are also critical to the level of customer service, as each customer is generally not able to receive service all day long and has its own time window for business transactions.Based on the aforementioned discussions, we propose a new type of delivery service with emphasis on variable VDs and time window constraints: the linehaul-feeder vehicle routing problem with virtual depots and time windows (LFVRPTW). The remainder of this paper is organized as follows. Section2 presents the literature review. Section 3 describes the problem. Section 4 proposes a solution algorithm. Section 5 solves and analyzes 16 test problems. Finally, Section 6 concludes with a few remarks.


## 2. Literature Review

The main issues related to city logistics have been investigated and a new problem class has been proposed by Crainic et al. [1]. In the past, a bunch of models and algorithms have been developed for evaluating and planning city logistics systems. Unfortunately, the new type of delivery service with emphasis on variable VDs and time window constraints, or more specifically the LFVRPTW, was not introduced.The LFVRPTW may be classified as a vehicle routing problem (VRP) [2, 3] with additional complexity generated by variable VDs and time window constraints. Since this research topic is relatively new in the logistics area, it has not attracted much attention in the literature.The LFVRPTW problem is similar to the truck and trailer problem [4, 5] in some aspects. In a truck and trailer problem, customers may exist in some places that are reachable only by trucks alone; therefore, a complete vehicle consisting of a truck and a trailer must perform an uncouple operation at a parking place. The truck will proceed alone to service the customers while leaving the trailer behind. After completing the services, the truck will return to the parking place and recouple with the trailer. The main difference between the LFVRPTW and the truck and trailer problem is that the trailer cannot move alone without a truck.The idea of VD is related to the cross-docking strategy, which has been adopted by global companies such as Wal-Mart and UPS to increase the speed of logistics and decrease inventory as well as to exploit high-capacity utilization for cheap full truckload transportation to the cross dock. In the cross-docking strategy, the time schedules of inbound and outbound trucks are well planned, so that the products can be moved directly from receiving docks to shipping docks without being stored in the distribution center [6–9]. In the LFVRPTW problem, however, the role of the distribution center is replaced by the VDs, and the products are directly transshipped from a large vehicle to one or more empty or near-empty smaller vehicles. A near-empty small vehicle is hereafter defined as a small vehicle on which the remaining load is not enough to fulfill the demand of the next customer along the scheduled route. Hence, the vehicle needs reloading before performing further services. Although the concept of cross-docking is related to VD, the latter is more difficult, because the number of VDs and their locations in a system may not be specified upfront and must be determined each time that a delivery operation is performed.When a VD is used for vehicles to clear their load, it can be thought of as the landfill in the Garbage Truck Routing Problem with Time Windows (GTRPTW). The GTRPTW problem is defined as finding a route that minimizes total travel cost when performing garbage collections at prespecified stops, subject to the time constraints. When a truck is fullen route, it should find a landfill to clear the load, that is, make a garbage disposal trip, before continuing its work. Each truck may need to make multiple disposal trips in a day. When a truck has serviced all of its customers, it must dump the garbage, even if the load is not full, before returning to the depot. Several papers have proposed workable solution algorithms that embed metaheuristics for solving the GTRPTW problem [10–14].The concept of the linehaul-feeder vehicle routing problem with prespecified virtual depot (LFVRP-PVD) was first identified by Tu et al. [15] and Chang et al. [16]. The LFVRP-PVD delivers lunch boxes to all customers using two sizes of vehicles. The empty or near-empty small vehicles can detour to the large vehicle situated at the prespecified single VD for reloading. However, no numerical data were provided. Chang [17] subsequently extended this work, renaming it the linehaul-feeder vehicle routing problem (LFVRP), and proposed a two-stage solution heuristics. In the first stage, the nearest neighbor method is employed to construct initial routes, while in the second stage, the initial solution is improved using the node exchange method. Computational experiments were conducted using simplified numerical data obtained from an international express delivery company in Taiwan. Seven strategies for determining the single VD are compared in terms of total travel costs.The common drawback associated with the LFVRP-PVD and LFVRP is the lack of flexibility due to prespecified VDs. This strict assumption has been relaxed by Chen et al. [18], resulting in the linehaul-feeder vehicle routing problem with virtual depots (LFVRP-VDs). To solve the LFVRP-VD, two two-stage heuristics were proposed. In the first stage, analogous to a so-called route-first cluster-second scheme, the giant tour concept considering reloading operations is proposed for constructing initial solutions; in the second stage a local search is adopted for improving the initial solution. The test problems, modified from a set of classical VRP benchmark situations, were extensively examined, and the two proposed heuristics were compared in terms of several selected performance measures. The results show that the more type-I customers that are available for the choice of VDs, the better objective value that can be obtained. However, time window constraints associated with customers are not considered in the LFVRP-VD. In the logistics market, customers are usually not open 24 hours a day; they must be serviced during a prespecified time window. In consideration of this additional requirement, a new research topic emerges: the linehaul-feeder vehicle routing problem with virtual depots and time windows (LFVRPTW).From the above brief literature review, it is clear that none of the existing articles has addressed both the issues of the variable VDs and time window constraints in a VRP environment, which thus naturally become the focus of this study.


## 3. Problem Description

To elaborate the LFVRPTW, Figure1 offers an illustration. The sample network contains one PD, four type-I customers (a,b,c,d), two VDs (b,d), and eleven type-II customers. A fleet consisting of one large vehicle and two small vehicles is dispatched from the PD; the corresponding three vehicle routes are constructed as follows:(i)
large vehicle route:PD→d(VD)→b(VD)→PD;(ii)
small vehicle 1 route:PD→2→3→d(VD)→7→9→10→PD;(iii)
small vehicle 2 route:PD→c→1→d(VD)→4→5→a→b(VD)→6→8→11→PD.Figure 1
Example of vehicle routes for the LFVRPTW.It is observed that only two of four type-I customers are actually chosen as VD, that is, nodesb and d. VD d conducts reloading service twice, while VD b conducts reloading service only once. The reloading service can be executed at a VD only when both the large vehicle and the small vehicle are present simultaneously. Since the other two type-I customers, that is, nodes a and c, are not chosen as a VD, they are serviced by small vehicle 2 based on the insertion cost.Figure2 depicts the time windows associated with each customer and illustrates how the large and small vehicles move on the time-space diagram. The PD, two non-VD type-I customers (nodes a and c), two VDs (nodes b and d), and eleven type-II customers (nodes 1 through 11) are on the x-axis. The y-axis indicates the time of day. The time window for customer 9 is [12, 17], which is denoted by a pair of triangles. Each customer is serviced by a vehicle that performs its service within the customer’s time window. The trajectory for the large vehicle is represented by bold arrows and the trajectories for the two small vehicles by thin arrows and dashed arrows, respectively. Small vehicle 1 departs from the PD at 8:00 am via intermediate nodes 2, 3, d, 7, 9, and 10 and returns around 16:00 pm. Small vehicle 2 departs from the PD at 11:00 am via intermediate nodes, c, 1, d, 4, 5, a, b, 6, 8, and 11 and returns around 20:00 pm. The travel time between nodes 2 and 3 by small vehicle 1 is represented by t23, and the service time needed at node 3 is denoted by s3. The time that the large vehicle remains at VD b is denoted by pb. Note that the waiting time for the large vehicle can be found by the length of stay minus the total time for reloading the small vehicles and servicing at the VD itself.Figure 2
Time-space diagram for the LFVRPTW.The LFVRPTW problem aims to minimize the total travel cost (including fixed and variable costs) for all vehicles. Three main constraints must be strictly complied with the following: (1) each customer must be serviced within a hard time window, which is known and fixed; (2) each small vehicle has a limited capacity, while the capacity of the large vehicle is not considered; (3) the total work time of each driver cannot exceed a preset maximum work time length. We also make the following assumptions.(1)
Only one PD exists.(2)
The location and demand of each customer are known and fixed.(3)
Customers are classified into two groups: type-I customers, which can be serviced by either the large vehicle or small vehicles, and type-II customers, which can only be serviced by small vehicles.(4)
Several small vehicles and a single large vehicle are used. The total cost is defined as the sum of the fixed cost (including rent and insurance) and variable cost (including the fuel cost and driver’s wage) for all vehicles. Thus, different travel costs are associated with different types of vehicles.(5)
A chosen VD is used for reloading, and each VD can be visited more than once by large and/or small vehicles.(6)
The large vehicle, in addition to serving VD customers, provides reloading service for empty or near-empty small vehicles.(7)
Empty or near-empty small vehicles can reload the commodity from the warehouse at the PD or from the large vehicle at VDs when they are present at the same time.(8)
The large vehicle will incur a waiting cost at a VD for reloading service in the event that it arrives earlier than the approaching small vehicles, and vice versa.(9)
The cost for reloading each small vehicle and for servicing each customer is known and fixed.Because of the complex characteristics listed above, the LFVRPTW is difficult to tackle, if not impossible, using the traditional VRP solution algorithm. A new solution algorithm is thus proposed.


## 4. Solution Algorithm

To solve the LFVRPTW problem, a two-stage solution algorithm is proposed. In the first stage, initial routes are constructed (see Section4.1); in the second stage, the initial solution is improved using the tabu search (see Section 4.2).


### 4.1. Initial Route Construction

Initial feasible routes must be constructed for both the large and small vehicles. Small vehicles are first routed to service all type-II customers subject to the three constraints previously described: customer time window, vehicle capacity, and driver work time limitation. When its loading is empty or near-empty, a small vehicle may choose either the PD or a VD for reloading if the corresponding saving is warranted. Consider that the VDs that currently perform worse may have the chance to improve in subsequent routes; the second best VD is also taken into account, but the maximum number of route branches for each vehicle is kept under 20.When small vehicle routes are constructed on a temporary or provisional basis, the large vehicle departs from the PD, services all VDs, and returns to the PD. Since the reloading operation at a VD can be executed only when both the matched small and large vehicles are present, late arrival of the large vehicle may affect the subsequent route plan of the matched small vehicle after reloading. If the subsequent route plan becomes infeasible, the unsatisfied customers remaining for the matched small vehicles after reloading need to be rescheduled.The general steps for generating initial routes are described as follows.Step 0 (Initialization).
Sort all unserviced type-II customers in order of time priority. If the time window constraint is the same, then the distance will be used to determine the order. The ordered customers are stored in the sequence list.Step 1.
Construct small vehicle routes to service all type-II customers in the sequence list.Step 2.
Construct the large vehicle route, and, if necessary, adjust the small vehicle routes.Step 3.
Select the best initial solution among all feasible solutions and stop.Steps1 and 2 are used to construct multiple small vehicle routes and a large vehicle route, respectively, which will be elaborated in the following in depth.


#### 4.1.1. Construction of Small Vehicle Routes

Multiple small vehicle routes can be formed by assigning the type-II customers in the sequence list to the small vehicles with minimum insertion cost (in terms of fixed and variable travel costs), while considering the criteria of customer time window, vehicle capacity, and driver work time limitations. If small vehicles are empty or near-empty, the cost of reloading incurred at each VD or PD is calculated and the results are compared; the two lowest cost depots are used for further exploration. This procedure with the consideration of reloading operations is repeated until all type-II customers have been inserted into small vehicle routes. The procedure for constructing multiple small vehicle routes using the minimum cost insertion method is described as follows.For each unserviced type-II customer in the sequence list, do the following.Step 1.
Check for the time window, vehicle capacity, and driver work time constraints.(1)
If three constraints are satisfied, compute the insertion cost on each feasible insertion position for all small vehicle routes. Go to Step2.(2)
If the customer cannot be inserted into any small vehicle route due to early arrival, compute the insertion cost for all small vehicle routes that could delay sufficient departure time from the PD. Go to Step2.(3)
If the customer cannot be inserted into any small vehicle route due to time window or driver work time constraints, go to Step2.(4)
If the customer cannot be inserted into any small vehicle route due to capacity constraints, compute the insertion cost that includes reloading cost from a chosen VD.Step 2.
Compute the incurred cost for dispatching a new, that is, additional, small vehicle from the PD to service the customer.Step 3.
Compare the computed insertion cost of the customer at all feasible positions for all small vehicle routes, and insert the customer into the route that exhibits the minimum insertion cost. Remove the inserted customer from the sequence list.
End ForStep1(1), the incurred insertion cost for unserviced customer k between two consecutive serviced type-II customers, that is, i and j, in a small vehicle route is computed as follows:(4.1)insertioncost=(costoftravelfromtype-IIcustomeritothenewlyscheduledtype-IIcustomerk)+(costoftravelfromthenewlyscheduledtype-IIcustomerktotype-IIcustomerj)-(costoftravelbetweencustomeriandcustomerjon⁡thesmallvehicleroute).Step1(4), the incurred insertion cost for a small vehicle to reload at a VD is computed as follows:(4.2)insertioncost=(costofthesmallvehiclemovingfromthecurrentcustomertotheselectedVDandfromtheVDtothenextcustomers)+(costofthelargevehiclemovingfromitscurrentVDtotheselectedVD(orPD)aswellasoperationalcostattheselectedVD(orPD)).Considering that the suboptimal choice of VD based on the current cost information may later outperform the optimal choice of VD, the second choice of VD is kept for further consideration. However, to avoid prohibitive increase of vehicle routes under consideration, we set the maximum number of route branching for each vehicle as equal to 20.


#### 4.1.2. Construction of the Large Vehicle Route

Based on the constructed small vehicle routes, the large vehicle route can be constructed accordingly. However, as mentioned, the reloading operation can be executed only when both the matched small and large vehicles are present at the selected VD at the same time. Therefore, late arrival of the large vehicle at the matched VD may cause the initially constructed small vehicle routes to become infeasible; hence, the subsequent route of the small vehicle needs to be rescheduled accordingly. In addition, each set of small vehicle routes generated in the previous section should construct a large vehicle route. The procedure for constructing a large vehicle route as well as rescheduling the small vehicle routes after reloading, if necessary, is described as follows.For each set of small vehicle routes, do the following.Step 1.
Construct a large vehicle route from the PD by connecting all selected VDs in chronological order, and go back to the PD. Multiple visits to each VD by the large vehicle are allowed if doing so is warranted in terms of total insertion cost. In this case, the VD type-I customer needs to be serviced only when it is visited by the large vehicle the first time. Note that non-VD type-I customers can be either inserted into the large vehicle route or serviced by a small vehicle depending on the incurred insertion cost.Step 2.
If late arrival occurs, update the arrival and departure time for all customers in subsequent portions of the routes for both the large vehicle and the small vehicles.Step 3.
For each small vehicle route, do the following.Check each customer in the subsequent route for the time window and driver’s work time constraints.
If the constraint(s) is not satisfied, remove the customer from the small vehicle route and connect its preceding and succeeding customers to form the new small vehicle subroute.Relabel the removed customer as “unserviced”.Update the arrival time and departure time of all customers in the subsequent route.
End ForStep 4.
For each unserviced type-II customer, do the following.For each small vehicle route, do the following.
Find all feasible insertion places, and compute the corresponding insertion costs for the unserviced type-II customer.
End For
Compute the incurred cost for dispatching a new small vehicle from the PD to service the customer.Compare the computed insertion cost of the customer among all possible routes, and insert the customer into the route with minimum insertion cost. Label the customer as “serviced”.
End ForStep 5.
For each unserviced non-VD type-I customer, do the following.For each large vehicle route or small vehicle route, do the following.
Find all feasible insertion places, and compute the corresponding insertion costs for the unserviced non-VD type-I customer.
End For
Compute the incurred cost for dispatching a new small vehicle from the PD to service the customer.Compare the computed insertion cost of the customer among all possible routes, and insert the customer into the route with minimum insertion cost. Label the customer as serviced.
End ForStep 6.
Stop upon the completion of initial solution construction, several initial solutions will be generated. However, in Step3 described in Section 4.1, only the initial solution with the lowest travel cost will be used for further improvement; this will be elaborated in the following section.


### 4.2. Improvement of Initial Solution

The initial solution is usually not optimal. To improve the quality of the initial solution, a local search method such as thek-opt exchange method is often used. However, due to the complexity of the LFVRPTW problem, this type of method is not ideal, because it is easily trapped within a local region. To avoid being stuck in a local region and to explore a wider area in the feasible region, metaheuristics methods such as the tabu search [19–21] offer great potential.The tabu search includes six components: initial solution, neighborhood solution, tabu list, aspiration criterion, move, and stopping criterion. The initial solution is generated in Section4.1. A neighborhood solution is usually obtained by relocating a node, that is, (1,0) operation, or exchanging selected nodes in pairs of routes, that is, (1,1) node exchange operation. The move refers to a change from one solution to another. The tabu list defines a set of unfavorable elements. While its tabu classification may be overridden, aspiration criterion requires that the new solution be better than the existing solution. The stopping criterion is set as a maximum number of iterations. The improvement procedure using the tabu search method is described as follows.Step 0.
Regard the initial solution as the incumbent (or known) best solution, denoted bySopt. Set iteration counter I=1, maximum tabu size Kmax=7, and maximum number of iterations Imax=100.Step 1.
Identify the neighborhood set using the (1,0) “relocate” operation. Compute the solutions in the neighborhood, and choose the best one.Step 2.
Perform a local search, that is, (1,1) node exchange method, on the above best solution.Step 3.
Identify the tabu list, or check for the aspiration criterion.Step 4.
Determine the currently best solution resulting from Steps2 and 3.Step 5.
Update the incumbent best solutionSopt with the current best solution if it improves the incumbent best solution; let I=I+1.Step 6.
When the termination rule is met, that is, eitherI=Imax, or the incumbent best solution cannot be improved in 10 consecutive iterations, stop.


## 4.1. Initial Route Construction

Initial feasible routes must be constructed for both the large and small vehicles. Small vehicles are first routed to service all type-II customers subject to the three constraints previously described: customer time window, vehicle capacity, and driver work time limitation. When its loading is empty or near-empty, a small vehicle may choose either the PD or a VD for reloading if the corresponding saving is warranted. Consider that the VDs that currently perform worse may have the chance to improve in subsequent routes; the second best VD is also taken into account, but the maximum number of route branches for each vehicle is kept under 20.When small vehicle routes are constructed on a temporary or provisional basis, the large vehicle departs from the PD, services all VDs, and returns to the PD. Since the reloading operation at a VD can be executed only when both the matched small and large vehicles are present, late arrival of the large vehicle may affect the subsequent route plan of the matched small vehicle after reloading. If the subsequent route plan becomes infeasible, the unsatisfied customers remaining for the matched small vehicles after reloading need to be rescheduled.The general steps for generating initial routes are described as follows.Step 0 (Initialization).
Sort all unserviced type-II customers in order of time priority. If the time window constraint is the same, then the distance will be used to determine the order. The ordered customers are stored in the sequence list.Step 1.
Construct small vehicle routes to service all type-II customers in the sequence list.Step 2.
Construct the large vehicle route, and, if necessary, adjust the small vehicle routes.Step 3.
Select the best initial solution among all feasible solutions and stop.Steps1 and 2 are used to construct multiple small vehicle routes and a large vehicle route, respectively, which will be elaborated in the following in depth.


### 4.1.1. Construction of Small Vehicle Routes

Multiple small vehicle routes can be formed by assigning the type-II customers in the sequence list to the small vehicles with minimum insertion cost (in terms of fixed and variable travel costs), while considering the criteria of customer time window, vehicle capacity, and driver work time limitations. If small vehicles are empty or near-empty, the cost of reloading incurred at each VD or PD is calculated and the results are compared; the two lowest cost depots are used for further exploration. This procedure with the consideration of reloading operations is repeated until all type-II customers have been inserted into small vehicle routes. The procedure for constructing multiple small vehicle routes using the minimum cost insertion method is described as follows.For each unserviced type-II customer in the sequence list, do the following.Step 1.
Check for the time window, vehicle capacity, and driver work time constraints.(1)
If three constraints are satisfied, compute the insertion cost on each feasible insertion position for all small vehicle routes. Go to Step2.(2)
If the customer cannot be inserted into any small vehicle route due to early arrival, compute the insertion cost for all small vehicle routes that could delay sufficient departure time from the PD. Go to Step2.(3)
If the customer cannot be inserted into any small vehicle route due to time window or driver work time constraints, go to Step2.(4)
If the customer cannot be inserted into any small vehicle route due to capacity constraints, compute the insertion cost that includes reloading cost from a chosen VD.Step 2.
Compute the incurred cost for dispatching a new, that is, additional, small vehicle from the PD to service the customer.Step 3.
Compare the computed insertion cost of the customer at all feasible positions for all small vehicle routes, and insert the customer into the route that exhibits the minimum insertion cost. Remove the inserted customer from the sequence list.
End ForStep1(1), the incurred insertion cost for unserviced customer k between two consecutive serviced type-II customers, that is, i and j, in a small vehicle route is computed as follows:(4.1)insertioncost=(costoftravelfromtype-IIcustomeritothenewlyscheduledtype-IIcustomerk)+(costoftravelfromthenewlyscheduledtype-IIcustomerktotype-IIcustomerj)-(costoftravelbetweencustomeriandcustomerjon⁡thesmallvehicleroute).Step1(4), the incurred insertion cost for a small vehicle to reload at a VD is computed as follows:(4.2)insertioncost=(costofthesmallvehiclemovingfromthecurrentcustomertotheselectedVDandfromtheVDtothenextcustomers)+(costofthelargevehiclemovingfromitscurrentVDtotheselectedVD(orPD)aswellasoperationalcostattheselectedVD(orPD)).Considering that the suboptimal choice of VD based on the current cost information may later outperform the optimal choice of VD, the second choice of VD is kept for further consideration. However, to avoid prohibitive increase of vehicle routes under consideration, we set the maximum number of route branching for each vehicle as equal to 20.


### 4.1.2. Construction of the Large Vehicle Route

Based on the constructed small vehicle routes, the large vehicle route can be constructed accordingly. However, as mentioned, the reloading operation can be executed only when both the matched small and large vehicles are present at the selected VD at the same time. Therefore, late arrival of the large vehicle at the matched VD may cause the initially constructed small vehicle routes to become infeasible; hence, the subsequent route of the small vehicle needs to be rescheduled accordingly. In addition, each set of small vehicle routes generated in the previous section should construct a large vehicle route. The procedure for constructing a large vehicle route as well as rescheduling the small vehicle routes after reloading, if necessary, is described as follows.For each set of small vehicle routes, do the following.Step 1.
Construct a large vehicle route from the PD by connecting all selected VDs in chronological order, and go back to the PD. Multiple visits to each VD by the large vehicle are allowed if doing so is warranted in terms of total insertion cost. In this case, the VD type-I customer needs to be serviced only when it is visited by the large vehicle the first time. Note that non-VD type-I customers can be either inserted into the large vehicle route or serviced by a small vehicle depending on the incurred insertion cost.Step 2.
If late arrival occurs, update the arrival and departure time for all customers in subsequent portions of the routes for both the large vehicle and the small vehicles.Step 3.
For each small vehicle route, do the following.Check each customer in the subsequent route for the time window and driver’s work time constraints.
If the constraint(s) is not satisfied, remove the customer from the small vehicle route and connect its preceding and succeeding customers to form the new small vehicle subroute.Relabel the removed customer as “unserviced”.Update the arrival time and departure time of all customers in the subsequent route.
End ForStep 4.
For each unserviced type-II customer, do the following.For each small vehicle route, do the following.
Find all feasible insertion places, and compute the corresponding insertion costs for the unserviced type-II customer.
End For
Compute the incurred cost for dispatching a new small vehicle from the PD to service the customer.Compare the computed insertion cost of the customer among all possible routes, and insert the customer into the route with minimum insertion cost. Label the customer as “serviced”.
End ForStep 5.
For each unserviced non-VD type-I customer, do the following.For each large vehicle route or small vehicle route, do the following.
Find all feasible insertion places, and compute the corresponding insertion costs for the unserviced non-VD type-I customer.
End For
Compute the incurred cost for dispatching a new small vehicle from the PD to service the customer.Compare the computed insertion cost of the customer among all possible routes, and insert the customer into the route with minimum insertion cost. Label the customer as serviced.
End ForStep 6.
Stop upon the completion of initial solution construction, several initial solutions will be generated. However, in Step3 described in Section 4.1, only the initial solution with the lowest travel cost will be used for further improvement; this will be elaborated in the following section.


## 4.1.1. Construction of Small Vehicle Routes

Multiple small vehicle routes can be formed by assigning the type-II customers in the sequence list to the small vehicles with minimum insertion cost (in terms of fixed and variable travel costs), while considering the criteria of customer time window, vehicle capacity, and driver work time limitations. If small vehicles are empty or near-empty, the cost of reloading incurred at each VD or PD is calculated and the results are compared; the two lowest cost depots are used for further exploration. This procedure with the consideration of reloading operations is repeated until all type-II customers have been inserted into small vehicle routes. The procedure for constructing multiple small vehicle routes using the minimum cost insertion method is described as follows.For each unserviced type-II customer in the sequence list, do the following.Step 1.
Check for the time window, vehicle capacity, and driver work time constraints.(1)
If three constraints are satisfied, compute the insertion cost on each feasible insertion position for all small vehicle routes. Go to Step2.(2)
If the customer cannot be inserted into any small vehicle route due to early arrival, compute the insertion cost for all small vehicle routes that could delay sufficient departure time from the PD. Go to Step2.(3)
If the customer cannot be inserted into any small vehicle route due to time window or driver work time constraints, go to Step2.(4)
If the customer cannot be inserted into any small vehicle route due to capacity constraints, compute the insertion cost that includes reloading cost from a chosen VD.Step 2.
Compute the incurred cost for dispatching a new, that is, additional, small vehicle from the PD to service the customer.Step 3.
Compare the computed insertion cost of the customer at all feasible positions for all small vehicle routes, and insert the customer into the route that exhibits the minimum insertion cost. Remove the inserted customer from the sequence list.
End ForStep1(1), the incurred insertion cost for unserviced customer k between two consecutive serviced type-II customers, that is, i and j, in a small vehicle route is computed as follows:(4.1)insertioncost=(costoftravelfromtype-IIcustomeritothenewlyscheduledtype-IIcustomerk)+(costoftravelfromthenewlyscheduledtype-IIcustomerktotype-IIcustomerj)-(costoftravelbetweencustomeriandcustomerjon⁡thesmallvehicleroute).Step1(4), the incurred insertion cost for a small vehicle to reload at a VD is computed as follows:(4.2)insertioncost=(costofthesmallvehiclemovingfromthecurrentcustomertotheselectedVDandfromtheVDtothenextcustomers)+(costofthelargevehiclemovingfromitscurrentVDtotheselectedVD(orPD)aswellasoperationalcostattheselectedVD(orPD)).Considering that the suboptimal choice of VD based on the current cost information may later outperform the optimal choice of VD, the second choice of VD is kept for further consideration. However, to avoid prohibitive increase of vehicle routes under consideration, we set the maximum number of route branching for each vehicle as equal to 20.


## 4.1.2. Construction of the Large Vehicle Route

Based on the constructed small vehicle routes, the large vehicle route can be constructed accordingly. However, as mentioned, the reloading operation can be executed only when both the matched small and large vehicles are present at the selected VD at the same time. Therefore, late arrival of the large vehicle at the matched VD may cause the initially constructed small vehicle routes to become infeasible; hence, the subsequent route of the small vehicle needs to be rescheduled accordingly. In addition, each set of small vehicle routes generated in the previous section should construct a large vehicle route. The procedure for constructing a large vehicle route as well as rescheduling the small vehicle routes after reloading, if necessary, is described as follows.For each set of small vehicle routes, do the following.Step 1.
Construct a large vehicle route from the PD by connecting all selected VDs in chronological order, and go back to the PD. Multiple visits to each VD by the large vehicle are allowed if doing so is warranted in terms of total insertion cost. In this case, the VD type-I customer needs to be serviced only when it is visited by the large vehicle the first time. Note that non-VD type-I customers can be either inserted into the large vehicle route or serviced by a small vehicle depending on the incurred insertion cost.Step 2.
If late arrival occurs, update the arrival and departure time for all customers in subsequent portions of the routes for both the large vehicle and the small vehicles.Step 3.
For each small vehicle route, do the following.Check each customer in the subsequent route for the time window and driver’s work time constraints.
If the constraint(s) is not satisfied, remove the customer from the small vehicle route and connect its preceding and succeeding customers to form the new small vehicle subroute.Relabel the removed customer as “unserviced”.Update the arrival time and departure time of all customers in the subsequent route.
End ForStep 4.
For each unserviced type-II customer, do the following.For each small vehicle route, do the following.
Find all feasible insertion places, and compute the corresponding insertion costs for the unserviced type-II customer.
End For
Compute the incurred cost for dispatching a new small vehicle from the PD to service the customer.Compare the computed insertion cost of the customer among all possible routes, and insert the customer into the route with minimum insertion cost. Label the customer as “serviced”.
End ForStep 5.
For each unserviced non-VD type-I customer, do the following.For each large vehicle route or small vehicle route, do the following.
Find all feasible insertion places, and compute the corresponding insertion costs for the unserviced non-VD type-I customer.
End For
Compute the incurred cost for dispatching a new small vehicle from the PD to service the customer.Compare the computed insertion cost of the customer among all possible routes, and insert the customer into the route with minimum insertion cost. Label the customer as serviced.
End ForStep 6.
Stop upon the completion of initial solution construction, several initial solutions will be generated. However, in Step3 described in Section 4.1, only the initial solution with the lowest travel cost will be used for further improvement; this will be elaborated in the following section.


## 4.2. Improvement of Initial Solution

The initial solution is usually not optimal. To improve the quality of the initial solution, a local search method such as thek-opt exchange method is often used. However, due to the complexity of the LFVRPTW problem, this type of method is not ideal, because it is easily trapped within a local region. To avoid being stuck in a local region and to explore a wider area in the feasible region, metaheuristics methods such as the tabu search [19–21] offer great potential.The tabu search includes six components: initial solution, neighborhood solution, tabu list, aspiration criterion, move, and stopping criterion. The initial solution is generated in Section4.1. A neighborhood solution is usually obtained by relocating a node, that is, (1,0) operation, or exchanging selected nodes in pairs of routes, that is, (1,1) node exchange operation. The move refers to a change from one solution to another. The tabu list defines a set of unfavorable elements. While its tabu classification may be overridden, aspiration criterion requires that the new solution be better than the existing solution. The stopping criterion is set as a maximum number of iterations. The improvement procedure using the tabu search method is described as follows.Step 0.
Regard the initial solution as the incumbent (or known) best solution, denoted bySopt. Set iteration counter I=1, maximum tabu size Kmax=7, and maximum number of iterations Imax=100.Step 1.
Identify the neighborhood set using the (1,0) “relocate” operation. Compute the solutions in the neighborhood, and choose the best one.Step 2.
Perform a local search, that is, (1,1) node exchange method, on the above best solution.Step 3.
Identify the tabu list, or check for the aspiration criterion.Step 4.
Determine the currently best solution resulting from Steps2 and 3.Step 5.
Update the incumbent best solutionSopt with the current best solution if it improves the incumbent best solution; let I=I+1.Step 6.
When the termination rule is met, that is, eitherI=Imax, or the incumbent best solution cannot be improved in 10 consecutive iterations, stop.


## 5. Test Results and Analysis

There are as yet no well-known and established benchmarks available in the literature for the version of the LFVRPTW studied in this paper. The behavior of the solution method proposed here can therefore not be tested using data instances that have been widely tested, and the results cannot be compared to the optimum or the best results obtained in previous publications.


### 5.1. Test Problems

We test our LFVRPTW problem using numerical examples. All the experiments were performed on a Microsoft Windows 7 personal computer equipped with Intel i5-460 M@ 2.53 GHz CPU, 4.00 GB memory. The sixteen test problems for the LFVRPTW were adopted from the VRP web site (http://neo.lcc.uma.es/radi-aeb/WebVRP/) with necessary modifications (see Table 1).Table 1
Sixteen test examples.
ProblemNetwork typeNumber of nodesSmall vehicle capacityDemand coefficientaVirtual depot candidatesbA32RS321002.04A34RM341002.04A38RM381002.04A45RM451002.04A46RM461002.04A61RM611001.44A60RS601001.94A64RS641001.84A65RM651002.04A69RM691002.04A80RS801002.04C51RS511602.04C81RS81602.04C161RS161602.04F45CM4520101.64F135CM13522101.74Resource: modified fromhttp://neo.lcc.uma.es/radi-aeb/WebVRP/.aDemand coefficient represents a multiplier to the original demand.bNumber of virtual depot candidates are set to four, one in each quadrant.General information associated with these problems is as follows:(1)
triangular inequality relations of customers distance are held in the network;(2)
all pairs of customers are connected;(3)
link travel distances of small vehicles are represented by the Euclidian distance between the two customers;(4)
link travel costs of small vehicles are represented by the corresponding link travel distances divided by 40 km/hr;(5)
the costs for a large vehicle (1200 cc van) include rent and insurance (NTD 1450/day), fuel cost (NTD 3.3/km), and driver’s wage (NTD 270/hr); and(6)
the costs for a small vehicle (125 cc motorcycle) consist of rent and insurance (NTD 600/day), fuel cost (NTD 0.77/km), and driver’s wage (NTD 120/hr).


### 5.2. Test Results

The sixteen examples for the LFVRPTW are tested. For comparison, the vehicle routing problem with time windows (VRPTW) using insertion method as well as node exchange method is also examined. Note that the VRPTW algorithm employed here is merely for comparative purposes, or more specifically to show a lower bound of the LFVRPTW solution obtained by our heuristics. Therefore, its computational efficiency is not a deep concern and may not be comparable with some algorithms described by Bräysy and Gendreau [2, 3]. However, this neglect should not affect the relation of LFVRPTW relative to VRPTW in the result and the analysis that follows. The test results for the LFVRPTW as well as the VRPTW are summarized in Table 2.Table 2
Test results for the LFVRPTW and the VRPTW.
Problem numberSolution algorithmObjective valueImprove. percentage of  initial solution (%)aNo. of small vehiclesCPU time (sec.)Depot numberbA32LFVRPTW112474.3683.52PD(1)VRPTW125412.95100.58—A34LFVRPTW103809.9583.21PD(2)VRPTW124441.52110.76—A38LFVRPTW1114220.8193.42PD(3)VRPTW126511.94111.18—A45LFVRPTW1351711.35104.66PD(3)VRPTW158572.47140.14—A46LFVRPTW125159.37104.75PD(3)VRPTW154994.45140.2—A60LFVRPTW2019413.63168.43PD(3)VRPTW208161.50170.16—A61LFVRPTW134507.32105.45PD(3)VRPTW145452.39130.11—A64LFVRPTW1906417.041511.7443(1),58(3)VRPTW220723.21180.24—A65LFVRPTW1942321.51126.13PD(1),24(2),45(3), 48(1),61(2)VRPTW214401.60190.16—A69LFVRPTW175919.19148.21PD(8)VRPTW209231.69190.26—A80LFVRPTW2729313.28136.7625(5),43(3),73(1)VRPTW274431.83210.24—C51LFVRPTW78967.0962.14—VRPTW79406.8870.20—C81LFVRPTW3219025.75196.3714(2),54(2)VRPTW394160.59270.23—C161LFVRPTW1201762.366621.36PD(1),43(3),83(1)VRPTW1252141.44741.55—F45LFVRPTW970411.4274.90PD(3)VRPTW98714.9780.63—F135LFVRPTW2175016.43157.77PD(2)VRPTW229392.27182.59—AverageLFVRPTW2297012.5514.896.79VRPTW251012.6018.750.59aThe tabu search is employed in the second stage of the proposed algorithm and the maximum number of iterations set for the tabu search method is 100.bNumbers in parenthesis denote the frequency of the depot being visited by the small vehicles.The computational results can be summarized as follows.(1)
In terms of objective values: all sixteen examples show that the objective values for the LFVRPTW are better than those for the VRPTW.(2)
In terms of number of small vehicles: all sixteen examples show that the number of small vehicles required for the LFVRPTW is fewer than that for the VRPTW. The average number of small vehicle routes required for LFVRPTW delivery operation is 14.89. Of the 16 test problems, 15 problems require fewer than 20 small vehicle routes, and one problem requires 66. The reason for the last solution is that the customers are randomly spread out over the network and located far away from the PD. In this situation, most of the small vehicle routes can only service one type-II customer due to driver work time constraints.(3)
In terms of computational times: it is observed that the average CPU times for the solutions are 6.79 sec. In these solutions, most of the computational times are used by the tabu search, resulting in an average improvement rate of about 12.25% (from an initial value of 25428 to a final value of 22970 in terms of average objective value).All 16 test problems indicate the advantage of the LFVRPTW over the VRPTW with respect to the objective value. This result confirms our conjecture that the LFVRPTW is advantageous over the VRPTW.


## 5.1. Test Problems

We test our LFVRPTW problem using numerical examples. All the experiments were performed on a Microsoft Windows 7 personal computer equipped with Intel i5-460 M@ 2.53 GHz CPU, 4.00 GB memory. The sixteen test problems for the LFVRPTW were adopted from the VRP web site (http://neo.lcc.uma.es/radi-aeb/WebVRP/) with necessary modifications (see Table 1).Table 1
Sixteen test examples.
ProblemNetwork typeNumber of nodesSmall vehicle capacityDemand coefficientaVirtual depot candidatesbA32RS321002.04A34RM341002.04A38RM381002.04A45RM451002.04A46RM461002.04A61RM611001.44A60RS601001.94A64RS641001.84A65RM651002.04A69RM691002.04A80RS801002.04C51RS511602.04C81RS81602.04C161RS161602.04F45CM4520101.64F135CM13522101.74Resource: modified fromhttp://neo.lcc.uma.es/radi-aeb/WebVRP/.aDemand coefficient represents a multiplier to the original demand.bNumber of virtual depot candidates are set to four, one in each quadrant.General information associated with these problems is as follows:(1)
triangular inequality relations of customers distance are held in the network;(2)
all pairs of customers are connected;(3)
link travel distances of small vehicles are represented by the Euclidian distance between the two customers;(4)
link travel costs of small vehicles are represented by the corresponding link travel distances divided by 40 km/hr;(5)
the costs for a large vehicle (1200 cc van) include rent and insurance (NTD 1450/day), fuel cost (NTD 3.3/km), and driver’s wage (NTD 270/hr); and(6)
the costs for a small vehicle (125 cc motorcycle) consist of rent and insurance (NTD 600/day), fuel cost (NTD 0.77/km), and driver’s wage (NTD 120/hr).


## 5.2. Test Results

The sixteen examples for the LFVRPTW are tested. For comparison, the vehicle routing problem with time windows (VRPTW) using insertion method as well as node exchange method is also examined. Note that the VRPTW algorithm employed here is merely for comparative purposes, or more specifically to show a lower bound of the LFVRPTW solution obtained by our heuristics. Therefore, its computational efficiency is not a deep concern and may not be comparable with some algorithms described by Bräysy and Gendreau [2, 3]. However, this neglect should not affect the relation of LFVRPTW relative to VRPTW in the result and the analysis that follows. The test results for the LFVRPTW as well as the VRPTW are summarized in Table 2.Table 2
Test results for the LFVRPTW and the VRPTW.
Problem numberSolution algorithmObjective valueImprove. percentage of  initial solution (%)aNo. of small vehiclesCPU time (sec.)Depot numberbA32LFVRPTW112474.3683.52PD(1)VRPTW125412.95100.58—A34LFVRPTW103809.9583.21PD(2)VRPTW124441.52110.76—A38LFVRPTW1114220.8193.42PD(3)VRPTW126511.94111.18—A45LFVRPTW1351711.35104.66PD(3)VRPTW158572.47140.14—A46LFVRPTW125159.37104.75PD(3)VRPTW154994.45140.2—A60LFVRPTW2019413.63168.43PD(3)VRPTW208161.50170.16—A61LFVRPTW134507.32105.45PD(3)VRPTW145452.39130.11—A64LFVRPTW1906417.041511.7443(1),58(3)VRPTW220723.21180.24—A65LFVRPTW1942321.51126.13PD(1),24(2),45(3), 48(1),61(2)VRPTW214401.60190.16—A69LFVRPTW175919.19148.21PD(8)VRPTW209231.69190.26—A80LFVRPTW2729313.28136.7625(5),43(3),73(1)VRPTW274431.83210.24—C51LFVRPTW78967.0962.14—VRPTW79406.8870.20—C81LFVRPTW3219025.75196.3714(2),54(2)VRPTW394160.59270.23—C161LFVRPTW1201762.366621.36PD(1),43(3),83(1)VRPTW1252141.44741.55—F45LFVRPTW970411.4274.90PD(3)VRPTW98714.9780.63—F135LFVRPTW2175016.43157.77PD(2)VRPTW229392.27182.59—AverageLFVRPTW2297012.5514.896.79VRPTW251012.6018.750.59aThe tabu search is employed in the second stage of the proposed algorithm and the maximum number of iterations set for the tabu search method is 100.bNumbers in parenthesis denote the frequency of the depot being visited by the small vehicles.The computational results can be summarized as follows.(1)
In terms of objective values: all sixteen examples show that the objective values for the LFVRPTW are better than those for the VRPTW.(2)
In terms of number of small vehicles: all sixteen examples show that the number of small vehicles required for the LFVRPTW is fewer than that for the VRPTW. The average number of small vehicle routes required for LFVRPTW delivery operation is 14.89. Of the 16 test problems, 15 problems require fewer than 20 small vehicle routes, and one problem requires 66. The reason for the last solution is that the customers are randomly spread out over the network and located far away from the PD. In this situation, most of the small vehicle routes can only service one type-II customer due to driver work time constraints.(3)
In terms of computational times: it is observed that the average CPU times for the solutions are 6.79 sec. In these solutions, most of the computational times are used by the tabu search, resulting in an average improvement rate of about 12.25% (from an initial value of 25428 to a final value of 22970 in terms of average objective value).All 16 test problems indicate the advantage of the LFVRPTW over the VRPTW with respect to the objective value. This result confirms our conjecture that the LFVRPTW is advantageous over the VRPTW.


## 6. Conclusion

This research has examined the LFVRPTW; the considered time windows and service times for reloading are more realistic but make the LFVRPTW much more difficult to solve. Therefore, in addition to the new problem type of the LFVRPTW, the major contribution of the paper is that a two-stage solution algorithm is developed for the LFVRPTW to demonstrate its advantage over the VRPTW. This two-stage solution algorithm generates an initial solution that considers reloading operations at both virtual and physical depots in the first stage and then, in the second stage, improves the quality of the obtained initial solution using the tabu method, which includes the (1,0) relocate operation as well as the (1,1) node exchange method. Compared with the VRPTW, the LFVRPTW is advantageous in terms of both objective value and the number of small vehicles required for dispatching. In addition, although the tabu search that is embedded in the second stage of the proposed solution algorithm consumes the major portion of the computational time for LFVRPTW, it yields an average improvement rate of 12.55%, which is an achievement well worth the cost when one comes to real applications.Several issues regarding computational efficiency and practical applications are worth further exploration. In view of the complexity of the LFVRPTW, multiple agent metaheuristics, such as genetic algorithm, ant colony optimization, and bee colony optimization, may be able to enhance further the overall computational efficiency and solution quality. The efficiency of the proposed algorithm should be comparable with existing VRPTW heuristics, such as those proposed by Cordeau et al. [22] and Moccia et al. [23].For practical applications, additional factors need to be considered, such as soft time window constraints, pickup and delivery operations, fixed number of small vehicles, and capacity constraint for the large vehicle. In addition, link travel times may differ due to traffic, road work, accidents, weather, and so forth. Therefore, time-dependent, rather than fixed, link travel times should be used in real-world problem solving. Furthermore, customers must be added or canceled in a real-time manner during delivery operation, because this situation is commonly seen in the real world.Finally, as for many other VRP problems, real applications for the LFVRPTW problem are essential. In this paper, the LFVRPTW was not demonstrated with real-world companies such as FedEx, DHL, and Black Cat-Takkyubin, because real data were not available. Nevertheless, this practical research should be conducted in the immediate future.



---

*Source: 759418-2011-12-07.xml*