INDUSTRIAL ENGINEERING APPLICATIONS IN TRANSPORTATION:LARGE-SCALE TRANSPORTATION NETWORK PLANNING
LARGE-SCALE TRANSPORTATION NETWORK PLANNING
Line-Haul Movement of Packages
During the pickup and delivery operation of a parcel delivery company, packages are picked up and brought to a local terminal, as discussed in Section 8. These packages are sometimes transported to their destination terminal directly and delivered to the customers. In most cases, however, packages go though a series of transfer terminals where they get sorted and consolidated. Transportation be- tween terminals is achieved using several modes of transportation. The most prevalent modes on the ground are highway and rail, using a fleet of tractors and trailers of different types. A fleet of aircraft is used for transporting by air.
A transfer terminal often shares the same building with one or more local terminals. Several sorting operations may be run daily in a transfer terminal and are repeated every day of the work week at the same times. A large transfer terminal may have four sorting operations at different times of the day or night. Packages get unloaded, sorted, and reloaded on trailers. Several types of trailers may be used with different capacities and other characteristics. One or more trailers are attached to a tractor and depart for the next terminal on their route. This may be another transfer terminal or their destination terminal, or a rail yard for the trailers to be loaded and transported by rail, or an air terminal, if the packages have to be transported by air. In this section, we will examine a model that determines the routes of packages from their origin to their destination terminals and the equip- ment used to transport them, only for packages that travel on the ground using two modes, highway or rail.
Package handling and transporting between terminals represents a large part of the operating costs for a package transportation company. A good operating plan that minimizes cost and / or improves service is crucial for efficient operations. In recent years, many new products and services have been introduced in response to customer demand. These changes as well as the changes in package volume require additions and modifications to the underlying transportation network to maintain its efficiency. A planning system that can evaluate alternatives in terms of their handling and transporting costs and their impact on current operations is very important. There is a tradeoff between the number of sorting operations a package goes through and the time needed to reach its destination. More sorting operations increase the handling cost, decrease the transportation cost because they consolidate loads better, but also increase the total time needed until a package is delivered to the customer. All these factors need to be taken into account in the design of a transportation network for routing packages.
A Network-Optimization Problem
The network-optimization problem for transporting packages on the ground can be defined as follows. Determine the routes of packages, mode of transportation (highway or rail), and types of equipment to minimize handling and transportation costs while the following constraints are met: service re- quirements are respected, the capacities of sorting operations are not surpassed, no sorting operation is underutilized, the number of doors of each facility available for loading trailers is considered, trailers balance by building, and all the packages to the same destination are routed along the same path.
To maintain level of service, packages must be transported between particular origin / destination (OD) pairs in a given time. The capacity of a sorting operation cannot be surpassed but also, if the number of packages through a sorting operation falls below a given value, the sorting operation needs to be closed down. The number of loading doors of each facility represents the maximum number of trailers that can be loaded simultaneously during a sorting operation. Note that two or more of the trailers loaded simultaneously may be going to the same terminal next on their route.
Trailers need to balance by building daily. This means that the trailers of each type that go into a building must also leave the building during the daily cycle. Balancing is achieved by introducing empty trailers into the system. There are several types of trailers that are used, with different capac- ities. Some types can be used both on highway and rail. Trailers can also be rented from the railroads, and these trailers may not need to balance. Each tractor can pull one, two, and, on rare occasions, three trailers, depending on the trailer types and highway restrictions. At a terminal, tractor–trailer combinations are broken up, the trailers unloaded, the packages sorted, the trailers loaded again, and the tractor and trailers reassembled to form new combinations. There is no constraint on the number of trailers of any type that are used.
An important operational constraint is that all the packages to the same destination must be routed along the same path. This implies that all packages with the same destination terminal follow the same path from the terminal where they first meet to their destination. This constraint results from the fact that sorting is done by destination. If sorting became totally automated, this constraint might be modified.
A network-optimization model can be used as a long-term planning tool. It can evaluate alter- natives for locating new building facilities, opening or closing sorting operations, and changing an operating plan when new products are introduced or the number of packages in the system changes. Because any such changes require retraining of the people who manually sort the packages, the routing network in parcel delivery is not changed often or extensively. For a network-optimization model to be used as an intermediate-term planning tool to modify the actual routing network, the model needs to obtain incremental changes, that is, to obtain solutions as close as possible to the current operations.
Modeling
The network-optimization problem is formulated on a network consisting of nodes that represent sorting operations and directed links that represent movement of packages from one sorting operation to another. Both the highway and rail modes are represented by one link if the same time is needed to traverse the link by either mode. If a different time is needed by each mode, two different links are used, each representing one mode. In the latter case, all the packages need to travel by only one mode even if both modes are feasible so that all the packages that start together arrive at the same time to their destination. It is assumed that every day is repeated unchanged without any distortion of the pattern because of weekends. Since a sorting operation is repeated every day at the same time, one node represents a sorting operation for as many days as necessary for a complete cycle of operations to occur in the system. To avoid any confusion, we will use in the description of the network design problem the terms origin and destination or OD pair to refer to the origin and destination nodes of a package; we will use the terms initial and final nodes to refer to the origin and destination nodes of a directed link.
Each node is characterized by a daily starting and ending time of the sorting operation, a sorting capacity, a sorting cost, and the number of loading doors available. Each link is characterized by a travel time and distance between its initial and final nodes and the types of combinations that are permitted on the link with their costs and capacities. The combinations representing both highway and rail are associated with the same link when the travel time is the same for highway and rail. If the travel time is different and the link represents a particular mode, only the combinations of this mode are associated with the link. In addition, for each OD pair, the number of packages that need to be transported is given as well as the maximum time permitted from the moment a package starts at its origin until it reaches its destination.
A network-optimization system that solves the problem presented above utilizes large amounts of data and must have a reliable data interface in addition to the solver. The data interface extracts, verifies, and validates the data needed for the problem corresponding to the particular geographical area applicable to the problem. It then generates the network and, after the solver is applied, produces reports of the results. The solver consists of optimization algorithms that obtain solutions of the problem.
The network described above can be very large. To facilitate the application of the optimization algorithms, the network size is reduced using various aggregation rules. OD pairs may be consolidated by building or destination group, and local terminals in the same building may be combined into one node. If all the possible connections between each pair of sorting operations are added, the network becomes very dense. For this reason, only links that are likely to be used in the solution are included (e.g., direct links between sorting operations that are farther apart than a given distance are omitted).
The network design problem is formulated below as a mixed-integer programming problem (MIP) (Nemhauser and Wolsey 1988). A graph G(N,E ) is given with N a set of nodes and E a set of directed links. A node represents a sorting operation for each consecutive day of a whole cycle of operations. A directed link (i, j) represents the movement of packages from sorting operation i (initial node of the link) to sorting operation j (final node of the link). Because of the presence of two different links that are used in parallel between the same sorting operations representing two different modes with different travel times, link (i, j) may not be unique. To simplify the presentation, however, we disregard the presence of parallel links. The formulation can be easily extended to include this case because at most one of such parallel links can be used in the solution. Additional notation is introduced next.
The cost dikl is estimated as the average cost of a package through sorting operation i E N multiplied by the number of packages of OD pair (k,l) E A. The cost cijm is estimated as a function of the distance of link (i, j) E E, fuel prices, driver wages as well as depreciation and cost of the trailer-combination type m E Mij.
It is assumed that all the packages processed through a sorting operation are available at the beginning and leave at the end of the sorting operation. The time hij of link (i, j) E E is the difference between the starting time of the sorting operation j and the ending time of the sorting operation i
with the appropriate time difference included for the packages to be transported on link (i, j) and be available at j on time. The time hij as defined above makes it unnecessary to consider the time windows of the sorting operations explicitly in the following formulation. The time hij is also equal to the travel time on link (i, j) plus the difference in time between the beginning of the sorting operation at j and the arrival of the packages at j, which corresponds to the wait time until the sorting operation j starts. The capacity of a sorting operation is represented by an upper bound that cannot be exceeded. A lower bound may also be used to force sorting operations to be closed if they are underutilized.
Network Design Formulation
The objective function (3) minimizes the total cost of handling and transporting the packages of all the OD pairs. Constraints (4) are balancing constraints ensuring that the packages of an OD pair start from their origin, end at their destination, and, if they enter an intermediate node, also exit the node. Each constraint (5) computes the departure time of the packages of OD pair (k,l) from node j, using the departure time of the preceding node i. If link (i, j) E E is used to transport the packages of OD pair (k,l) E A ( yijkl = 1), the constraint becomes tjkl - tikl ;:: hij + rj. If link (i, j) E E is not used ( yijkl = 0), the constraint is not binding. The starting time at each origin is set with constraints (6).
Constraints (7) ensure that the service requirements are met, that is, the movement of the packages of OD pair (k,l) from their origin k to their destination l takes no more than Tkl time. These constraints also force constraints (5) to apply with equality if necessary.
Constraints (8) ensure that the capacities of the sorting operations are not violated, and constraints (9) prevent sorting operations that are open from being underutilized. Constraints (10) ensure that packages enter node j only if the sorting operation j is open. That is, if yijkl = 1 for any i, j, k, l then zj = 1 from constraints (10). If yijkl = 0 for all i, j, k, l then zj = 0 from constraints (9) and (10).
Constraints (11) ensure that all the packages going though sorting operation i and having the same destination l use the same network link to the next sorting operation on their path, that is, there are no split paths to the same destination. The only case that is permitted is k -= k', j = j'. The case
k = k', j -= j' is excluded by constraints (4) which ensure a unique path for each OD pair (k,l). The
case k -= k', j -= j' is excluded by constraints (11). Using k < k' avoids repeating the constraints
(11) twice.
Constraints (12) are balancing constraints ensuring that for each building Bk and for each trailer type q E F that must balance, the same number of trailers that enter building Bk also exit it. To achieve balancing of trailers, empty trailers may be introduced into the system by constraints (12). These constraints are more complicated than they would be if each trailer-combination type rather than each trailer type needed to balance. Constraints (13) are the volume constraints, ensuring that
for each link (i, j) trailers with enough capacity are used to transport the number of packages on the link.
Constraints (14) ensure that the number of trailers that are filled during a sorting operation is no larger than the number of available loading doors. It is assumed that at most one trailer is filled from each door during a sorting operation. This is a good approximation although it may be conservative at times because occasionally it is possible to fill a trailer at a door and replace it with a new trailer during the same sorting operation. Constraints (15) ensure that the number of nonempty trailers of type q E Q, on link (i, j) E E represented by wijq is no larger than the total number of trailers of type q E Q (empty and nonempty) forming the trailer combinations of type m E Mij on link (i, j) E E represented by xijm. Note that wijq can have alternative solution values in the previous formulation apart from being exactly equal to the number of nonempty trailers. The value of wijq is always at least as large as the number of nonempty trailers from constraint (13). If empty trailers are introduced for balancing so that constraint (15) is not binding, wijq can have alternative solution values larger than the number of nonempty trailers, depending on how tight the corresponding con- straint (14) is. Constraints (16) to (20) are the integrality and nonnegativity constraints.
For a large transportation company, the G(N,E) network may have 40,000 links even when care is taken to keep it as sparse as possible. The number of binary variables yijkl of the above MIP formulation may be 14,000,000 or more. That is also the number of constraints (5), while the number of constraints (11) is much larger.
Formulation (3)–(20) is too large to be supplied to an MIP solver and solved directly. Instead, a heuristic solution for the network design problem can be obtained by solving sequentially two smaller problems that are embedded in formulation (3)–(20). These are the package-routing problem and the trailer-assignment problem. In the first step, the routes of the packages are obtained assuming a representative trailer type for highway and rail. This step produces the number of packages that are transported from the initial node to the final node of each link of the network. In the second step, given the number of packages and the types of permitted equipment on each link, the actual modes and trailer combinations that balance are obtained. These two problems are presented next.
Package-Routing Problem
The package-routing problem determines the routes of packages on the G(N,E) network for each OD pair so that the service requirements are met, the capacities of the sorting operations are not exceeded, the sorting operations are not underutilized, the number of loading doors of the buildings is not exceeded, packages to a common destination are routed along the same path, trailers are not under- utilized, and total cost is minimized. The package-routing problem does not determine the trailer combinations that are used, nor does it balance trailer types.
In the following, we still present a simplified formulation where we do not indicate mode, although we continue to use one link for both modes if the travel times are the same for both modes on the link and two different links if the travel times are different. We extract from formulation (3)–(20) constraints (4)–(8), (18), and (20), which involve only the yijkl and tjkl variables, putting aside for the moment the constraints on the number of loading doors, underutilized sorting operations, split paths to common destination, and maximization of trailer utilization. Because of their very large number, constraints (11) are not included.
Because the objective function (3) involves variables other than yijkl and tjkl, we replace it with a new objective function that uses an estimated cost parameter. First, we select a representative trailer- combination type for each mode and estimate the cost per package, per mode for each link by dividing the combination cost on the link by the combination capacity. For links that share both modes, the smaller cost of the two modes is used. Using the cost per package, the following cost parameter is computed:
The MIP formulation (22), (4)–(8), (18), and (20) of the package-routing problem is still a very large problem and difficult to solve directly. If the complicating constraints (8) are removed, the problem is solved relatively easily. We take advantage of this characteristic by using a Lagrangian relaxation approach (Ahuja et al. 1993; Fisher 1985; Geoffrion 1974). This is combined with search heuristics that also implement the constraints that are completely omitted in the formulation, which are the constraints on the number of loading doors, the lower bound constraints on the capacity of each sorting operation that is open, the split paths constraints, and an additional lower bound constraint on the number of packages on any link (i, j) E E that is actually used. The last constraint forces more efficient trailer utilization by ensuring that no link carries too few packages, which would result in the use of trailers with very low load factors in the trailer-assignment step.
The following Lagrangian dual problem is obtained by dualizing constraints (8) using their non- negative Lagrange multipliers Aj, j E N.
Lagrangian Relaxation of the Package-Routing
finds a path from an origin k E N to a destination l E N with the smallest cost that has total time no greater than Tkl. Although the constrained shortest-path problem is NP-complete, it can be used as part of an algorithm for the package-routing problem because there are several algorithms that solve large enough problems in good computer running times (Ahuja et al. 1993; Desrosiers et al. 1995).
A heuristic algorithm for the package-routing problem is presented next, based on the previous analysis. It is applied to the network described before that includes only one link between a pair of sorting operations representing the cheaper mode if the times hij for both modes are the same, and two links, one for each mode, if the times are different. A more detailed (but still high-level) de- scription of each step follows the algorithm.
Package-Routing Heuristic Algorithm
1. Find the OD pairs that have a unique feasible path from their origin to their destination using a k-shortest path algorithm. Route all the packages with unique shortest paths along the ob- tained paths, remove them from the package-routing problem, and update all the parameters.
2. Solve a constrained shortest path for each OD pair using the costs cijkl = cijkl + Ajvkl, where the Lagrange multipliers are set to zero for the first iteration.
3. Reroute packages to (i) eliminate split paths from each sorting operation to a common desti- nation, (ii) eliminate split paths between different modes that have different times on links so that only one mode is used, (iii) enforce the capacity constraint, and (iv) enforce the constraint on the number of loading doors for each sorting operation.
4. If the solution can be improved and the limit on the number of Lagrangian iterations is not reached, compute new costs cijkl using subgradient optimization or some other methodology and go to step 2.
5. Reroute packages from underutilized links to consolidate loads while preserving solution feas- ibility.
6. Reroute packages to close the underutilized sorting operation that is permitted to be closed and realizes the most savings. If a sorting operation is closed, disable the node representing it and start over from step 2.
In step 1, a k-shortest path algorithm (Minieka 1978) for k = 2 is used to obtain all the OD pairs that have unique feasible paths. The packages of these OD pairs are routed along their single paths and removed from the problem, updating all the parameters.
![clip_image002[1]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKvkiMelRFd06n-F25PMO4blSeDAotZjEzNai8R7oyspopjDBUDdOD2Nz6kMP4FFd2GJnKS_CsNj6gXV3Rggk67zB3sU6z5taLfXUlfZoJbhvUCX6pa4REzFUMQAMNE3Dxz7LpNWKuaG1Q/s1600-h/clip_image00212.gif "clip_image002[1]"){kind=small}
Step 3 takes care of the split-paths, capacity, and loading-door constraints. Each node of the network is examined if it satisfies the split-paths constraints (11). If multiple paths to the same destination exist starting from the node, the best path is selected based on several criteria and all the packages from the node to the common destination are routed along this path. Also, if packages are split between two parallel links of different modes, they are rerouted along only one parallel link. Each node is also examined to find whether it satisfies the capacity constraints (8). For each node that surpasses the permitted capacity, OD pairs that use the node are selected according to several criteria and their packages are removed until the capacities are satisfied. The removed packages are routed again sequentially using the constrained shortest-path algorithm on a network where the nodes that have reached their capacities are disabled. The split-paths constraints and the capacity constraints are examined repeatedly until they are satisfied or the algorithm indicates that it cannot find a feasible solution. Finally, each node is examined if it satisfies constraint (14) on the number of loading doors. If a node is found that violates the door constraint, packages are rerouted to sequentially reduce the number of doors but keep the capacity and split constraints valid.
![clip_image002[2]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5zSe9p9FBOzxd2bY7HSwWaRnm9TMSF9lDQwTUg5xx9kfmFWdHlZ4wprtcuMF5jlM1XD2r9XaFhpvkfUHqDxHMSnjzdrHtjU37J1kY9H8IbLxbZsYZ12x2vpQB7oHBIZfX4khESZuy5OQf/s1600-h/clip_image00222.gif "clip_image002[2]"){kind=small}
In step 5, links are found that carry too few packages for a complete load and the packages are rerouted so that the capacity, split-paths, and door constraints continue to be satisfied. These con-
straints are included to improve the results of the trailer-assignment problem that is solved after the package-routing problem and that represents the true cost of a network design solution.
Finally, in step 6, underutilized sorting operations are examined to implement constraints (9). The packages of underutilized sorting operations are rerouted and the underutilized sorting operation for which the total cost of the solution decreases most is eliminated. The node representing the eliminated sorting operation is disabled and the algorithm starts over from step 2.
The routing decisions obtained by the package-routing heuristic algorithm outlined above are used as input in the trailer-assignment problem that is described next.
Trailer-Assignment Problem
Given the number of packages on each link obtained by solving the package-routing problem, the trailer-assignment problem determines the number and type of trailer combinations on each link of the network G(N,E ) that have enough combined capacity to transport all the packages on the link, balance by trailer type for each building, and have the least cost.
The trailer-assignment problem is described next. To solve the problem more efficiently, the network G(N,E ) can be modified into the network G'(N',E') as follows. Each node i E N' represents a building, that is, all the nodes representing sorting operations in the same building are collapsed into one node. All the links that carry packages in the solution of the package-routing problem are included. Among the links in G(N,E ) that do not carry packages, only those that may be used to carry empty combinations for balancing are included so that E' � E. In particular, among parallel links between buildings that do not carry packages, only one is retained in G'. Still, the network G' generally has several parallel links between each pair of nodes, in which case link (i, j) is not unique. To avoid complicating the formulation and because it is easy to extend it to include parallel links, we will not include indexing to indicate parallel links, exactly as we did in formulation (3)–(20).
The trailer-assignment problem is formulated below on the network G'(N',E') using constraints (12), (13), and (16) as well as the objective function (3) with some modifications.
Objective function (31) is the same as objective function (3). It does not include the first component because it is a constant since the values of the yijkl variables are known from the solution of the package-routing problem. Constraints (32) are the same as constraints (12) except that the summation over buildings is now unnecessary because a node represents a building. Constraints (33) are similar to constraints (13) where, as in the objective function, the number of packages, vij, for all OD pairs on link (i, j) is now a constant. The variables wijq are not needed anymore and only the variables xijm are used, representing combinations with both full and empty trailers. So the trailer capacities kq for q E Q are replaced by the trailer-combination capacities km for m E Mij.
The integer-programming (IP) problem (31)–(34) is still difficult to solve. If constraints (32) are removed, the problem without balancing is easy to solve because it breaks into many very small problems, one for each link. To take advantage of this characteristic, Lagrangian relaxation (Ahuja et al. 1993; Fisher 1985; Geoffrion 1974) is used to solve problem (31)–(34), dualizing the balancing
constraints (32). A Lagrange multiplier Ajq, unrestricted in sign, is used for each balancing constraint and the following Lagrangian dual problem is obtained.
where cijm = cijm + LqEF 8qm (Ajq - Aiq) is the modified cost of moving trailer-combination type
m E Mij on link (i, j) E E' given the vector A.
Problem (35)–(37) decomposes into lE'l subproblems, one for each link (i, j) E E'. Each one of the subproblems is a kind of integer reverse knapsack problem, similar to the integer knapsack problem (Martello and Toth 1990; Nemhauser and Wolsey 1988; Chva´tal 1983) and can be solved by similar algorithms. Each subproblem is very small, having lMijl variables for link (i, j) E E'. The solution obtained by solving the Lagrangian dual (i.e., all the reverse knapsack problems) does not necessarily balance trailer combinations at each node even for optimal A and is not generally feasible for the original problem (31)–(34). A feasible solution is obtained heuristically by solving sequentially one minimum-cost-flow problem (Ahuja et al. 1993) for each trailer type that needs to balance. Balancing is achieved by adding empty trailers or replacing one trailer type with another one of larger capacity that is not yet balanced or does not need to balance.
A Lagrangian relaxation heuristic algorithm that solves the Lagrangian dual problem (35)–(37) is presented next. It uses subgradient optimization to compute the Lagrange multipliers A.
Lagrangian Relaxation Algorithm for the Trailer-Assignment Problem
1. Set the Lagrange multipliers A to zero in the Lagrangian dual problem and initialize Z (upper bound, best known feasible solution of the original problem) to a high value.
2. Solve the Lagrangian dual problem with the latest values of A (by solving a set of integer reverse knapsack problems) to obtain the optimal objective function value, Z*(x*, A), for the given A.
3. Apply a heuristic approach to obtain a feasible solution of the problem and update Z.
4. If the gap between Z and Z*(x*, A) is small or some other criterion is satisfied (e.g., a set number of iterations is reached or no more improvement is expected), stop.
5. Compute new values of the Lagrange multipliers A using subgradient optimization and go to step 2.
Step 3 above may be implemented only occasionally instead of at every iteration. Improvement heuristics can also be used to modify the solution in several ways. They can be used to combine single trailers into more efficient trailer combinations. They can also be used to find any cycles of trailer types that are either empty or can be replaced by trailer types that do not need to balance. If a whole cycle of trailers that results in improved cost is modified, balancing of trailers is maintained. Improvement heuristics can also be used to replace whole cycles of trailers of excess capacity with trailers of smaller capacity if the total cost is decreased.
A subgradient optimization algorithm (Ahuja et al. 1993; Crowder 1976) is used in step 5 to compute an improved Lagrange multiplier vector and is described below.
Subgradient Optimization Algorithm
Given an initial Lagrange multiplier vector A0, the subgradient optimization algorithm generates a sequence of vectors A0, A1, A2, . . . If Ak is the Lagrange multiplier already obtained, Ak+1 is generated by the rule
where tk is a positive scalar called the step size and pk is a scalar that satisfies the condition 0 < pk ::: 2. The denominator of equation (38) is the square of the Euclidean norm of the subgradient vector corresponding to the optimal solution vector xk of the relaxed problem at step k. Often a good rule for determining the sequence pk is to set p0 = 2 initially and then halve pk whenever Z*(x*, Ak) has not increased in a specific number of iterations. The costs are calculated with the new values of A. If any negative costs are obtained, the value of p is halved and the values of A recomputed until all the costs are nonnegative or p is too small to continue iterating.
A feasible solution is obtained in step 3, using a minimum-cost-flow algorithm (Ahuja et al. 1993) sequentially for each trailer type that needs to balance. First, for each building the excess or deficit of trailers of each type that has to balance is computed. Then a minimum-cost-flow algorithm is applied for each trailer type that obtains the optimal movements of trailers from each node of excess to each node of deficit. This may be the movement of a single empty trailer, the movement of an empty trailer that gets attached to an already used trailer to make up a permitted combination, or the movement of an already used trailer replacing another trailer type of smaller or equal capacity that is not yet balanced or does not need to balance.
Lagrangian relaxation is often used within a branch-and-bound procedure. The exact branch-and- bound algorithm has large computational cost; also, the trailer-assignment problem is only part of a heuristic algorithm for the network design problem. For these reasons, the Lagrangian relaxation algorithm is applied only once, at the root of the branch-and-bound tree, to find a heuristic solution to the trailer-assignment problem.
Extensions of the Network-Design Problem
If the results of the network-design problem are intended not only for long-term planning but to actually modify the routing network, the solution must represent an incremental change from the currently used solution. Otherwise, any savings from an improved solution may be lost in modifying the sorting operations to accommodate the solution changes. To this end, both the package-routing and the trailer-assignment problem can be modified relatively easily to handle presetting some of the variables. For the package-routing problem, this means presetting whole or partial paths of specific OD pairs. A solution is obtained by preprocessing the input data to eliminate or modify OD pairs that are completely or partially preset and updating the input data. Similarly, for the trailer-assignment problem, particular combinations on links may be preset. After appropriate variables are fixed, the Lagrangian relaxation algorithm optimizes the remaining variables.
The network-design problem presented considers only packages moving on the ground and chooses only one transportation mode when travel times differ between sorting operations. The network-design problem can be extended to include all modes of transportation and all types of products with different levels of service requirements. Different modes may have different costs and travel times between sorting operations, permitting parallel use of modes with different travel times along the same routes. This extension complicates considerably an already difficult problem and is not described here any further.
Comments
Post a Comment