Springer Series in Operations Research Altiok: Performance Analysis of Manufacturing Systems Bramel and Simchi-Levi: The Logic of Logistics: Theory, Algorithms, and Applications for Logi[r]
W hat Is Logistics M a n a g e m e n t?
In today's competitive global markets, manufacturers are increasingly prioritizing their logistics systems due to short product life cycles and rising customer expectations The rapid advancement of communication and transportation technologies, such as mobile communication and overnight delivery, has further driven the ongoing evolution of logistics management.
In modern logistics systems, products are manufactured in factories, stored in warehouses, and then distributed to retailers or customers To enhance service levels and minimize costs, logistics strategies must consider the interactions among suppliers, manufacturing centers, warehouses, distribution centers, and retail outlets This comprehensive logistics network also includes the movement of raw materials, work-in-process inventory, and finished goods between these facilities.
This book aims to showcase the latest advancements in logistics management, which is defined by the Council of Logistics Management as the systematic process of planning, executing, and overseeing the efficient flow and storage of goods, services, and relevant information from their origin to the final consumer, all while meeting customer demands.
This definition leads to several observations First, logistics management takes into consideration every facility that has an impact on system effectiveness and
E x am p les
Logistics management plays a crucial role in ensuring that products meet customer requirements by coordinating activities from suppliers and manufacturing facilities to warehouses and retailers Its primary objective is to achieve efficiency and cost-effectiveness throughout the entire logistics system, focusing on minimizing overall costs associated with transportation, distribution, and inventory management of raw materials, work-in-process, and finished goods This approach emphasizes a comprehensive systems perspective rather than merely reducing transportation costs or inventory levels Furthermore, logistics management involves planning, implementing, and controlling the logistics network, integrating various activities across strategic, tactical, and operational levels within the organization.
Indeed, following Hax and Candea’s (1984) treatment of production-inventory systems, logistical decisions are typically classified in the following way.
Strategic decision-making significantly impacts a firm's long-term success, encompassing choices about the number, location, and capacity of warehouses and manufacturing facilities, as well as the management of material flow within the logistics network.
The tactical level involves decision-making that is revised periodically, usually between quarterly and annually This encompasses essential aspects such as purchasing and production choices, inventory management strategies, and transportation plans, including how often customers are visited.
• The o p eratio n al level refers to day-to-day decisions such as scheduling, routing and loading trucks.
This section presents key logistics management issues that underpin the problems explored in the initial four parts of the book These issues encompass a wide range of logistics management decisions across the three previously mentioned levels Our aim is to succinctly introduce the questions and trade-offs related to these critical decisions.
In a scenario where multiple plants supply products to geographically diverse retailers, the existing warehouse network may be inadequate Management is considering a reorganization of the distribution system, prompted by factors such as shifting demand patterns or the expiration of lease agreements for certain warehouses These changes could necessitate adjustments in plant production levels, the selection of new suppliers, and an overall redesign of the goods flow throughout the distribution network.
The distribution network aims to optimize warehouse locations and capacities, establish production levels for each product at various plants, and determine transportation flows between facilities This strategic approach seeks to minimize total production, inventory, and transportation costs while meeting essential service level requirements.
A manufacturing facility must efficiently produce to meet known product demand over a specified timeframe, often supported by advance orders or contracts Production costs include fixed expenses, such as machine setup, and variable costs based on unit production time Additionally, holding costs accumulate for each unit in inventory The primary goal for planners is to fulfill demand in each period while minimizing total production and inventory costs throughout the fixed horizon This challenge intensifies with an increasing number of products manufactured.
Retailers managing inventory face the challenge of unpredictable customer demand, relying on probabilistic distribution to inform their decisions Their primary goal is to establish optimal reorder points and order quantities Ordering costs comprise a fixed fee, such as transportation expenses, and a variable cost based on the quantity ordered Additionally, a linear inventory holding cost is incurred over time for each product unit To minimize the expected costs associated with ordering and holding inventory, retailers must develop an effective inventory policy, a task that becomes increasingly complex as the variety of products increases and ordering costs vary with the selected items.
Wal-Mart's recent success underscores the significance of cross docking, a logistics strategy where central warehouses function as coordinators and transshipment points for incoming orders without holding inventory This raises critical questions regarding the optimal number of cross docking points needed, the potential savings from this strategy, and the practical implementation of cross docking in operations.
A warehouse supports multiple retailers by offering a diverse range of products, necessitating a careful balance between inventory and transportation costs to minimize overall expenses The tradeoff involves frequent, smaller shipments that lower inventory costs but increase transportation costs, versus infrequent, larger shipments that result in higher inventory costs but reduced transportation expenses Assuming constant demand from each retailer, the goal is to develop an effective inventory policy and transportation strategy that outlines vehicle routes, schedules, and the frequency of retailer visits, ultimately aiming to reduce both inventory and transportation costs across the system.
A warehouse supplies products to retailers using a limited-capacity fleet of vehicles, with a dispatcher responsible for load assignments and route planning The dispatcher must first group retailers based on load compatibility with vehicle capacity and then determine the optimal sequence to minimize costs This involves choosing between two cost functions: minimizing the number of vehicles used or reducing the total distance traveled The scenario exemplifies a single-depot Capacitated Vehicle Routing Problem (CVRP), where a fleet of vehicles, starting from the warehouse depot, aims to serve customers while minimizing the total route length.
Efficient truck routing is crucial for timely deliveries from a warehouse to retailers, as the order of visits impacts both delivery duration and return time This scenario exemplifies the Traveling Salesman Problem (TSP), where the goal is to determine the shortest route, minimizing either time or distance Thus, optimizing truck routes is an essential aspect of effective fleet management.
The Bin-Packing Problem (BPP) is a critical challenge in logistics, where the goal is to efficiently pack items into boxes, bins, or vehicles with limited capacity, minimizing the number of bins utilized This problem is particularly relevant in the context of the Capacitated Vehicle Routing Problem (CVRP), where the aim is to reduce the number of vehicles needed for product delivery Additionally, bin packing has diverse applications, such as optimizing the cutting of standard-length materials.
6 1 In tro d u ctio n wire or paper strips into specific custom er order sizes It also often appears as a subproblem in other combinatorial problems.
Delivering products to retailers or customers often requires adherence to specific time windows, such as a delivery between 9 AM and 11 AM When retailers set these time constraints, it complicates the challenge of determining vehicle routes that satisfy both capacity and time window requirements.
In certain distribution systems, customers designate specific pickup and delivery locations, requiring dispatchers to efficiently coordinate these logistics Each customer’s pickup and delivery must be managed by a single truck to minimize total travel distance Consequently, the truck routes must adhere to vehicle capacity limits, comply with time-window restrictions for each pickup and delivery, and ensure that pickups occur prior to their corresponding deliveries.
M odeling Logistics Problems
This book focuses on well-defined mathematical problems and issues in logistics, while acknowledging that many important topics, such as information systems, outsourcing, and strategic partnerships, are challenging to quantify and will not be addressed For a comprehensive analysis of these complex subjects, readers are directed to the forthcoming book by Simchi-Levi et al (1997).
The fact that the examples provided in the previous section can be defined mathematically is, obviously, meaningless unless all required data are available
Finding, verifying, and tabulating logistics data can be highly problematic due to challenges in determining inventory holding costs, production costs, additional vehicle expenses, and warehouse capacities Additionally, identifying the relevant data for specific logistics issues adds complexity to the data collection process Even when data is available, modeling real-world problems is fraught with difficulties, as it often excludes critical factors such as travel time variations, production yield fluctuations, inventory shrinkage, forecasting, and crew scheduling, which significantly complicate logistics operations.
For most o f this book, we assume that all relevant data, for example, production costs, production times, warehouse fixed costs, travel times, holding costs, etc., are
Logistics in P r a c t i c e
given As a result, each logistics problem analyzed in Parts I-IV is well defined and thus merely a mathematical problem.
Logistics problems are addressed in practice through various approaches that have proven effective over time Companies often rely on past successes, such as maintaining last year's safety stock levels to prevent backlogs or sticking with proven delivery routes to ensure timely shipments Additionally, logistics managers frequently utilize "rules of thumb," like the "20/80 rule," which emphasizes focusing on the 20% of products that account for 80% of costs In logistics network design, similar heuristics guide decisions, suggesting optimal warehouse locations based on service areas, such as placing a single warehouse in Chicago for nationwide coverage or using Los Angeles and Atlanta for two warehouses Lastly, some organizations leverage the expertise of logistics professionals, applying strategies that have benefited competitors to enhance their own operations.
While various logistics strategies can be appealing, the effectiveness of a tailored approach may be compromised without focusing on the optimal solution for specific cases The rise of affordable computing power has enabled firms of all sizes to utilize advanced decision support systems that optimize logistics strategies These systems allow users to input, review, and validate data, execute algorithms, and present user-friendly solutions When accurate data is provided and the correct problem is addressed, these systems can significantly lower overall costs Typically, achieving a satisfactory solution involves an iterative process where users evaluate different scenarios and their effects on costs and service levels, making it a valuable tool for decision-making, even if it doesn't strictly adhere to traditional optimization methods.
These systems are fundamentally based on models and algorithms, often serving as computerized adaptations of established rules of thumb Increasingly, they incorporate advanced techniques derived from the fields of operations research, management science, and computer science.
In this book, we present the current state-of-the-art in mathematical research in the area o f logistics M ost o f the problems listed above have at their core extremely
Combinatorial problems classified as NP-Hard present significant challenges, making it highly unlikely to develop an algorithm that can consistently deliver the optimal solution within polynomial time relative to the problem's size For those interested in a deeper understanding of computational complexity, Garey and Johnson's 1979 book is a valuable resource Consequently, achieving a consistently optimal solution is often deemed unattainable, leading to the use of heuristic or approximation methods in many scenarios.
Evaluation of Solution T ech n iq u es
Evaluating heuristic or approximation methods is a key research question, encompassing techniques that vary from simple rules of thumb to complex mathematical programming These methods aim to deliver good solutions within a reasonable timeframe, although the definitions of "good" and "reasonable" are context-dependent, varying by heuristic and problem instance The acceptable time frame for solutions can also be influenced by the specific environment in which the heuristic is applied, particularly in scenarios requiring real-time logistics problem-solving Therefore, assessing and quantifying the effectiveness of a heuristic remains a critical focus, with traditional evaluation methods being employed for this purpose.
Empirical comparisons involve selecting a representative sample of problems to evaluate the performance of various heuristics, focusing on solution quality, computation time, or both A significant challenge of this approach is identifying an appropriate set of test problems, as a heuristic may excel in one scenario but falter in another As noted by Fisher (1995), this inconsistency often leads practitioners to modify the heuristic, resulting in increased complexity While such efforts can yield a tailored algorithm that performs well in specific situations, it typically becomes highly sensitive to data changes and may struggle when applied in different contexts.
Worst-case analysis evaluates the maximum deviation from optimality that a heuristic can incur across various problem instances, measured by relative error For instance, a heuristic for the Bin Packing Problem (BPP) may ensure that any solution it generates uses no more than 50% additional bins compared to the optimal solution Similarly, a heuristic for the Traveling Salesman Problem (TSP) might guarantee that the route it provides is at most twice the length of the optimal route Such guarantees help mitigate concerns about suboptimality by assuring users that the solutions are within a defined percentage of optimality However, one significant drawback of this approach remains.
Additional Topics
A heuristic can excel in typical real-world scenarios but may struggle significantly with specific, unusual cases Therefore, when evaluating algorithms, a heuristic that offers superior worst-case performance guarantees does not automatically indicate greater practical effectiveness.
Average-case analysis aims to evaluate a heuristic's performance by measuring the average relative error between the heuristic solution and the optimal solution, based on specific assumptions about the distribution of problem data These assumptions can encompass various factors such as depot location, demand size, item size, time windows, and vehicle capacities While this method can provide valuable insights, it has notable limitations, particularly the requirement for large problem sizes to yield meaningful results For instance, in the Bin Packing Problem (BPP), if item sizes are uniformly distributed between zero and the bin capacity, a heuristic can be effectively assessed through average-case analysis.
The "close to optimal" approach involves sorting items in nonincreasing order and pairing each item with the largest compatible item, starting with the largest This method demonstrates that as the problem size increases, the relative error between the heuristic solution and the optimal solution diminishes towards zero However, a significant limitation is that conducting an average-case analysis often requires assuming independent customer behavior, which complicates the process Additionally, identifying suitable probabilistic assumptions for specific real-world scenarios poses a considerable challenge.
We concur with Fisher (1980) that the various approaches in logistics should be viewed as complementary rather than competitive, due to their respective advantages and potential drawbacks Our experience indicates that the most effective logistics algorithms in practice tend to excel in at least two of the key performance measures.
Assessing the worst-case or average-case performance of a heuristic can be technically challenging Consequently, while a heuristic might excel on average or in the worst-case scenario, demonstrating this performance may exceed our current capabilities.
Due to space and time constraints, we have had to omit several important findings, such as those related to yield management, machine scheduling, random yield in production, and dynamic and stochastic fleet management models For comprehensive surveys on these topics, we recommend referring to the works of Graves et al (1993) and Ball et al (1995) Additionally, while there are many robust solutions available for specific logistics problems, numerous areas remain underexplored.
As models become increasingly complex and incorporate various practical issues, their analysis becomes more challenging.
Logistics management is a field where rigorous mathematical analysis produces elegant results and significantly influences practical applications in logistics.
I n tr o d u c tio n
Logistics management plays a crucial role in ensuring that products meet customer requirements by coordinating activities from suppliers and manufacturing facilities to warehouses and retailers The primary objective is to achieve efficiency and cost-effectiveness throughout the entire logistics system, focusing on minimizing overall costs related to transportation, distribution, and inventory management of raw materials, work in progress, and finished goods This approach emphasizes a comprehensive systems perspective rather than merely reducing transportation costs or inventory levels Additionally, logistics management involves planning, implementing, and controlling the logistics network, integrating various activities across strategic, tactical, and operational levels within the organization.
Indeed, following Hax and Candea’s (1984) treatment of production-inventory systems, logistical decisions are typically classified in the following way.
Strategic decisions significantly impact a firm's long-term success, encompassing critical choices about the number, location, and capacity of warehouses and manufacturing plants, as well as the management of material flow within the logistics network.
The tactical level involves decision-making processes that are revised on a quarterly to annual basis This encompasses crucial aspects such as purchasing and production choices, inventory management policies, and transportation strategies, including how often customers are visited.
• The o p eratio n al level refers to day-to-day decisions such as scheduling, routing and loading trucks.
This section outlines key logistics management challenges that underpin the problems explored in the initial four parts of the book These challenges encompass a wide range of logistics management decisions across the three previously mentioned levels Our aim is to succinctly present the questions and trade-offs linked to these critical decisions.
In a scenario where multiple plants supply products to geographically dispersed retailers, the existing warehouse network may be inadequate, prompting management to consider a reorganization or redesign of the distribution system Factors such as shifting demand patterns or the end of leasing contracts for certain warehouses can drive this need for change Consequently, these evolving demand patterns may require adjustments in plant production levels, the selection of new suppliers, and an overall reconfiguration of the goods flow within the distribution network.
The objective of optimizing the distribution network is to strategically select warehouse locations and capacities, establish production levels for each product at various plants, and determine efficient transportation flows between facilities This approach aims to minimize total production, inventory, and transportation costs while meeting specified service level requirements.
A manufacturing facility must efficiently produce goods to meet known demand within a specified timeframe, often based on advance orders or signed contracts Production costs include fixed costs, such as machine setup, and variable costs related to unit production time Additionally, holding costs accrue for each unit in inventory The primary goal for planners is to fulfill demand while minimizing total production and inventory expenses throughout the designated period As the number of products increases, the complexity of this challenge escalates significantly.
Retailers face the challenge of managing inventory for products with unpredictable customer demand, relying on probabilistic demand distributions Their primary goal is to establish optimal reorder points and determine order quantities Ordering costs are comprised of a fixed fee, such as transportation from the warehouse, and a variable cost that scales with the number of items ordered Additionally, retailers incur a linear holding cost that accumulates over time for each product To minimize the expected costs associated with ordering and holding inventory, retailers must develop effective inventory policies, a task that becomes increasingly complex as the variety of products increases and order costs vary based on the selected items.
Wal-Mart's recent achievements underscore the significance of a logistics strategy known as cross docking, where central warehouses serve as coordinators and transshipment points for incoming orders without holding inventory This approach raises essential questions regarding the optimal number of cross docking points needed, the potential savings generated through this strategy, and the practical implementation steps required for effective execution.
A warehouse supports multiple retailers by managing a diverse range of products To optimize operating costs, management must find the right balance between inventory and transportation expenses Frequent deliveries result in smaller shipments, leading to lower inventory costs but higher transportation costs Conversely, infrequent deliveries involve larger shipments, which increase inventory costs while reducing transportation expenses Assuming consistent demand from each retailer, the goal is to develop an effective inventory policy and transportation strategy that outlines vehicle routes, schedules, and visit frequency to minimize overall inventory and transportation costs.
A warehouse supplies products to retailers using a limited-capacity fleet of vehicles, with a dispatcher responsible for assigning loads and determining routes The dispatcher must first group retailers based on their load capacity to ensure feasibility for each vehicle Next, the dispatcher decides on the sequence of deliveries to minimize costs, focusing on either reducing the number of vehicles used or minimizing total distance traveled This process exemplifies the single-depot Capacitated Vehicle Routing Problem (CVRP), where a fleet must serve customers from a depot, aiming to establish vehicle routes that achieve the shortest total distance.
Efficient truck routing is crucial for timely product deliveries from a warehouse to retailers, as the order of visits directly impacts delivery duration and return time The challenge of determining the shortest route, whether in time or distance, exemplifies the Traveling Salesman Problem (TSP) Thus, optimizing truck routes is a key aspect of effective fleet management.
The Bin-Packing Problem (BPP) is a crucial challenge in logistics, where the goal is to efficiently pack items into boxes, bins, or vehicles with limited capacity while minimizing the number of bins used This problem is particularly relevant in the context of the Capacitated Vehicle Routing Problem (CVRP), where the aim is to reduce the number of vehicles required for product delivery Additionally, bin-packing techniques are applicable in various other scenarios, such as optimizing the cutting of standard lengths.
6 1 In tro d u ctio n wire or paper strips into specific custom er order sizes It also often appears as a subproblem in other combinatorial problems.
Delivering products to retailers or customers often requires adherence to specific time windows, such as a delivery between 9 AM and 11 AM When retailers set these time constraints, it complicates the challenge of determining vehicle routes that satisfy both capacity and time window requirements.
In certain distribution systems, customers designate specific pickup and delivery locations, necessitating careful coordination by the dispatcher to ensure that each customer’s pickup and delivery pair is managed by a single truck To optimize efficiency, the dispatcher must minimize the total distance traveled while adhering to vehicle capacity limits and time-window constraints for each pickup and delivery Additionally, it is essential that each pickup occurs prior to its corresponding delivery.
The Bin-Packing P r o b l e m
First-Fit and B e st-F it
The proof o f the worst-case bounds for FF and BF, the first part o f Theorem 2.2.2, is based on the following observation Recall XF or BF.
L em m a 2.2.3 Consider the jth bin opened by X F ( j > 2) A n y item that was assigned to it before it was more than h a lffu ll does not f i t in any bin opened by
The property is proven to be true for First-Fit (FF) and extends to any item assigned to the jth bin (where j > 2), regardless of whether it was assigned before the bin became more than half full To demonstrate this for Best-Fit (BF), we assume, for contradiction, that item i was assigned to the jth bin while it was still less than half full, and that it could fit into an already opened bin, specifically the kth bin This implies that item i cannot be the first item in the jth bin, as BF would not have opened a new bin if it could fit into an existing one Let the levels of bins k and j just before item i was packed be ak and aj, with item h being the first item in bin j According to our hypothesis, we have wh < aj < 1 Since BF places items in the bin with the largest available capacity, and item i would have fit in bin k, it follows that aj must be greater than ak However, since ak is less than 1, this leads to the conclusion that item h could also fit in bin k, which creates a contradiction.
We use Lem m a 2.2.3 to construct a lower bound on the minimum num ber o f bins For this purpose, we introduce the following procedure For a given integer v,
Select v bins from those generated by XF, ensuring that 2 < v < bXF(L) Index these v bins sequentially from 1 to v based on the order they are opened For each bin j (where j ranges from 1 to v), let Xj represent the set of items assigned by XF to that bin before it exceeded half its capacity Additionally, define Sj as the complete set of items assigned to the jth bin by XF It is important to note that Xj is a subset of Sj for all j from 1 to v.
P ro ced u re LB B P (L ow er B ound B in-Packing)
Else, let u be the smallest item in X j.
According to Lemma 2.2.3, Procedure LBBP produces nonempty subsets S1, S2, , Sm, where m is less than v, ensuring that the sum of weights YieS for j less than m - 1 is greater than 1, and possibly for j equal to m This occurs because, as defined in the LBBP procedure, item u, initially assigned to bin j when it was not more than half full, cannot be placed in any bin i where i is less than j Consequently, this leads to the following conclusion.
The bins generated by Procedure LBBP, specifically bins 1 to m-1, are not feasible, leading to the conclusion that the total weight of items assigned exceeds m-1 Each item from the set of items indexed from m+1 onward is allocated to exactly one of the subsets Sj, where j ranges from 1 to m-1, and possibly to Sm If Sm is feasible, meaning no additional items are assigned to it, then the total weight of items assigned to the subsets is less than m-1 Conversely, if an item is assigned to Sm, then the subsets Sj are rendered infeasible, confirming that the total weight is less than the threshold defined by the subsets.
We are prepared to demonstrate the initial part of Theorem 2.2.2, which involves establishing an upper limit on the absolute performance ratio of the XF heuristic Let c represent the count of large items in the list L For the sake of argument, we will assume that bXF(L) > c; if this were not the case, the solution generated by XF would be optimal Thus, the difference bXF(L) - c > 0 indicates the number of type I bins produced by XF We will analyze two distinct cases.
Case 1: c is even In this case we partition the bins produced by XF into two sets
The initial set consists solely of type I bins, while the subsequent set encompasses all type II bins produced by XF Index the type I bins in the first set sequentially from 1 to bXF(L) — c Define v as bXF(L) — c, and implement Procedure LBBP on the type I bins, resulting in m bins, of which at least m — 1 are deemed infeasible.
L em m a 2.2.5 I f c is even, max | - + m, 2(bXF(L) — m) — — J < b*(L).
In an optimal solution, the sum of the weights of large items in any bin must be less than the bin's capacity, leading to the inequality \( Y_{ie}L_{wi} < b + (L) \) Additionally, based on Lemma 2.2.4 and the constraint that no two large items can occupy the same bin, we derive \( Y_{ie}L_{wi} > m - 1 + 2 \) Given that \( c \) is even, it follows that \( m + 2 < b*(L) \).
Since we applied Procedure LBBP only to the type I bins produced by XF, each one o f these bins has at least two items except possibly one w hich may have only
20 2 W orst-C ase A n aly sis one item Hence, 2(bXF(L) — m — c — 1) + 1 < \ U ”=m+1 X j \ and therefore, using Lemma 2.2.4,
Rearranging the left-hand side gives the second lower bound I
Proof From Lemma 2.2.5 we have 2(bXF(L) — m) — y < b*(L) Hence, bXF(L) < b ! L + ^ + m y J ~ 2 4 b*(L) c c
- 4 v h since m + 2, b*(L) and c are lower bounds I
Case 2: c is odd In this case we partition the set of all bins generated by the XF heuristic in a slightly different way The first set o f bins, called B 1, comprise all the type I bins except the last type I b in opened by XF The second set is made up o f the remaining bins; that is, these are all the type II bins together w ith the type
I b in not included in B 1 We now apply procedure LBBP to the bins in B1 (with v = bXF(L) — c — 1), producing m bins out o f w hich at least m — 1 bins are not feasible.
Proof Take one o f the type II bins and “match” it w ith the only type I bin not in
B1; the total w eight o f these two bins is more than 1 Thus, using Property 2.2, we have c—L + 1 + (m — 1) < S ie L w i < b *(L) w hich proves the first lower bound
To prove the second lower bound, we use the fact that every bin in B 1 has at least 2 items and therefore 2(bXF(L) — m — c — 1) < \ U v=m+1 X j \ Using Property 2.2, we get
2.2 The Bin-Packing Problem 21 or
Rearranging the left-hand side gives the second lower bound I
Proof From Lemma 2.2.7 we have 2(bXF(L) — m) — 3f — 2 — b* (L) Hence,
First-Fit Decreasing and Best-Fit D e c r e a s i n g
The worst-case bounds for First-Fit Decreasing (FFD) and Best-Fit Decreasing (BFD) heuristics are established based on Lemma 2.2.3 This lemma asserts that if a bin produced by these heuristics contains items no larger than size 1, then the first two items allocated to that bin cannot fit into any previously opened bins.
Let XFD represent either FFD or BFD, and index the bins created by XFD in the order they are opened We examine three scenarios, starting with the case where bXFD(L) equals 3p for some integer p greater than 1 In this scenario, if the bin indexed at 2p + 1 contains a large item, then it follows that b*(L) is greater than 2p, which is twice bXFD(L) Conversely, if this bin does not contain a large item, then bins indexed from 2p + 1 to 3p must collectively hold at least 2p - 1 small items that cannot fit into the first 2p bins Consequently, the total size of the items exceeds 2p - 1, leading to the conclusion that b*(L) is indeed greater than 2p, confirming that b*(L) is greater than or equal to bXFD(L).
If bXFD(L) equals 3p + 1 and bin 2p + 1 holds a large item, the process is complete However, if it does not, bins 2p + 1 to 3p + 1 must contain at least 2p + 1 small items, which cannot fit into the first 2p bins This situation indicates that the total size of the items exceeds 2p, leading to the conclusion that b*(L) is greater than 2p + 1, thereby confirming that b*(L) surpasses bXFD(L).
If bXFD(L) equals 3p + 2, and bin 2p + 2 contains a large item, the process is complete However, if bin 2p + 2 does not contain a large item, then the bins from 2p + 2 to 3p + 2 must hold at least 2p + 1 small items Since none of these small items can fit into the first 2p + 1 bins, it follows that the total size of the items exceeds 2p + 1, leading to the conclusion that b*(L) is greater than 2p + 2, which is also greater than |bXFD(L).
The Traveling Salesman P r o b l e m
A M inimum Spanning Tree Based H e u ris tic
This algorithm demonstrates that a fixed worst-case bound of 2 is achievable for the Traveling Salesman Problem (TSP) when the distance matrix adheres to the triangle inequality assumption Consequently, the heuristic guarantees a solution with a total length no more than 100% greater than that of the optimal tour.
A spanning tree of a graph G = (V, E) is a connected subgraph that includes all vertices |V| with |V| - 1 edges The cost of a tree is determined by the sum of the lengths of its edges, and a minimum spanning tree (MST) is defined as a spanning tree with the lowest possible cost It is established that finding a minimum spanning tree can be accomplished in polynomial time, as noted by Papadimitriou and Steiglitz (1982) Additionally, if W* represents the weight of the minimum spanning tree, it follows that W* ≤ L*, since removing any edge from the optimal tour yields a spanning tree.
The minimum spanning tree can efficiently identify a feasible traveling salesman tour in polynomial time This process involves conducting a depth-first search on the minimum spanning tree, as outlined by Aho et al (1974), followed by implementing straightforward enhancements.
24 2 W orst-C ase A n aly sis on this solution Formally, this is done as follows (Johnson and Papadimitriou, 1985).
A M inim um S pan n in g Tree B ased H euristic
Step 1: Construct a minimum spanning tree and color its edges white, and all other edges black.
Step 2: Let the current vertex (denoted v) be an arbitrary vertex.
Step 3: If one o f the edges adjacent to v in the M ST is white, color it black and proceed to the vertex at the other end o f this edge Else (all edges from v are black), go back along the edge by which the current vertex was originally reached.
Step 4: Let this vertex be v Stop if v is the vertex you started w ith and all edges o f M ST are black Otherwise go to Step 3.
The strategy outlined generates a tour that begins and concludes at a specific vertex, visiting all other vertices in the graph while covering each arc twice However, this approach is not particularly efficient, as it may result in some vertices being visited multiple times.
To enhance this tour, we can implement a shortcut strategy that bypasses previously visited vertices, allowing us to proceed directly to the next unvisited vertex This adjustment, supported by the triangle inequality assumption, ensures that the tour length will not increase and may even decrease.
Let LMST be the length o f the traveling salesman tour generated by the above strategy We clearly have
Lmst — 2W* — 2L*, where the first inequality follows since without shortcuts the length o f the tour is exactly 2W * This proves that the w orst case bound o f the algorithm is at m ost 2
To verify that the worst-case bound of this heuristic is optimal, we refer to the example presented by Johnson and Papadimitriou (1985) in Figure 2.1, where W* is defined as | + 1(1 — e) + 2e — 1, L MST ô + t (1 — e), and L* equals f.
The Nearest Insertion H e u r i s t i c
The Nearest Neighbor Heuristic is an intuitive strategy for solving the Traveling Salesman Problem (TSP) It begins by selecting an arbitrary starting vertex and then identifying the closest unvisited vertex to travel to next This process continues until all vertices have been visited, after which the route returns to the original starting point.
Rosenkrantz et al (1977) demonstrate a family of instances for the Traveling Salesman Problem (TSP) with arbitrary values of n, highlighting that the tour length produced by the Nearest Neighbor Heuristic for each instance in this family exhibits a specific characteristic.
The tour generated by the
Minimum Spanning Tree Based Algorithm
FIGURE 2.1 An example for the minimum spanning tree based algorithm with n 26 2 W orst-C ase A n aly sis
O (log n) times the length o f the optimal tour Thus, the Nearest Neighbor Heuristic does not have a bounded worst-case performance.
The algorithm's inherent weakness lies in its "greedy" strategy, which initially performs well by incorporating short arcs into the path However, this approach ultimately leads to longer arcs, particularly evident in the final edge that connects the last node back to the starting node This issue arises because the heuristic fails to account for the positions of the starting vertex and potential ending vertices throughout the process.
The Nearest Insertion (NI) Heuristic, developed by Rosenkrantz et al., enhances the performance of the Nearest Neighbor Heuristic This method constructs a Hamiltonian cycle that includes a subset of vertices during each iteration The heuristic identifies the closest vertex not yet in the cycle and inserts it between two adjacent vertices This process continues until all vertices are included in the cycle, thereby optimizing the overall route.
The N earest In sertio n H euristic
Step 1: Choose an arbitrary node v and let the cycle C consist o f only v.
Step 2: Find a node outside C closest to a node in C; call it k.
Step 3: Find an edge {i, j} in C such that dik + dkj - dij is minimal.
Step 4: Construct a new cycle C by replacing {i, j} w ith {i, k} and {k, j}.
Step 5: If the current cycle C contains all the vertices, stop Otherwise, go to Step 2.
Let L NI be the length o f the solution obtained by the Nearest Insertion Heuristic Then:
T heorem 2.3.3 For all instances o f the TSP satisfying the triangle inequality,
We start by proving the following interesting result Let T be a spanning tree o f
G and let W (T) be the weight (cost) o f that tree; that is, W (T) is the sum o f the length of all edges in the tree T Then:
L em m a 2.3.4 For every spanning tree T,
We demonstrate the lemma by associating each vertex added during the algorithm's execution with a unique edge from the specified tree T This is achieved through a procedure that operates concurrently with the Nearest Insertion Heuristic.
2.3 The T raveling S alesm an P roblem 27
The D ual N earest In se rtio n P ro ced u re
Step 1: Start w ith a family T o f trees that, at first, consists o f only the tree T.
Step 2: Given k (the vertex selected in Step 2 o f NI), find the unique tree in T containing k Let this tree be Tk.
Step 3: Let t be the unique vertex in Tk that is in the current cycle.
Step 4: Let h be the vertex adjacent to t on the unique path from t to k Replace
Tk in T by two trees obtained from Tk by deleting edge {t, h}.
Step 5: If T contains n trees, stop Otherwise, go to Step 2.
The Dual Nearest Insertion procedure operates concurrently with the Nearest Insertion Heuristic, executing corresponding steps in both methods simultaneously Specifically, whenever Step 1 is completed in the Nearest Insertion Heuristic, Step 1 is also executed in the Dual Nearest Insertion procedure, and this pattern continues for Step 2 and subsequent steps.
In Step 4 of the Dual Nearest Insertion procedure, the set of trees T is updated, ensuring that each tree contains exactly one vertex from the current cycle, while each vertex of the current cycle is assigned to only one tree This occurs when edge {t, h} is removed, resulting in the formation of two subtrees: one that includes vertex t and another that includes vertex k, with edge {t, h} representing the insertion of vertex k.
In the current cycle, let vertex m represent the closest vertex to k, which is outside the cycle, making dkm the smallest distance compared to all duv where u is in the cycle and v is outside The adjacent vertex m + 1 is one of the vertices on the cycle next to m When edge {i, j} is removed from the current cycle, inserting vertex k increases the tour length by the formula dik + dkj - dij - dmk + dk,m+1 - dm,m+1 - 2dmk This calculation holds true under the assumption of the triangle inequality and is applicable only when the cycle consists of at least two vertices.
When the Nearest Insertion algorithm first enters Step 2 with exactly one vertex, adding vertex k to the current cycle increases the tour length by precisely 2dmk.
In the current cycle, since t is included and h is excluded, the difference is represented as dmk — dth Consequently, the cost increase for the current cycle is limited to 2dth This relationship is consistent across every edge of T and the respective inserted vertex.
To finish the proof o f Theorem 2.3.3, apply Theorem 2.3.4 w ith T*; thus,
This completes the proof o f the Theorem.
The tour generated by the Nearest Insertion Algorithm
FIGURE 2.2 An example for the nearest insertion algorithm with rt = 8.
To illustrate the tightness of the bound, we refer to the example by Rosenkrantz et al (1977) shown in Figure 2.2, where each edge connecting consecutive perimeter vertices measures 1, while all other edges are 2 Consequently, the optimal traveling salesman tour visits the vertices in the order they appear on the circle, resulting in L* = n Furthermore, the Nearest Insertion Heuristic produces the tour illustrated in Figure 2.2(b), demonstrating its cost-effectiveness.
Christofides’ H e u ris tic
In 1976, Christofides introduced a straightforward algorithm that is recognized for having the best-known worst-case performance bound for the Traveling Salesman Problem (TSP) To effectively explain this algorithm, it is essential to outline several key properties of graphs.
Lemma 2.3.5 Given a graph with a t least two vertices, the num ber o f vertices with odd degree is even.
Definition 2.3.6 A Eulerian Tour is a tour that traverses all edges o f a graph exactly once.
Definition 2.3.7 A Eulerian Graph is a graph that has a Eulerian Tour.
Then it is a simple exercise to show the following.
Lemma 2.3.8 A connected graph is Eulerian i f and only i f the degree o f each vertex is even.
Christofides’ algorithm starts with a minimum spanning tree O f course, this tree (as any other tree) is not Eulerian since some of the vertices have odd degree
To transform a graph into an Eulerian graph, we can add specific arcs that connect vertices with odd degrees, ensuring they become even degree vertices This process involves identifying a minimum weight matching among the odd degree vertices to achieve the desired configuration.
2.3 The T raveling S alesm an P roblem 29
Given a graph w ith an even number o f vertices, a matching is a subset o f edges w ith the property that every vertex is the end-point o f exactly one edge o f the subset
The minimum weight matching problem aims to identify a matching with the lowest total edge length This optimization challenge can be efficiently solved in O(n^3) time complexity, where n represents the number of vertices in the graph, as detailed by Lawler (1976).
According to Lemma 2.3.5, the number of vertices with odd degree in the Minimum Spanning Tree (MST) is even, which allows for the addition of edges from a matching on these odd degree vertices, thereby increasing their degree by one This transformation results in an Eulerian graph, as stated in Lemma 2.3.8 To minimize costs, it is essential to choose edges from a minimum weight matching The Eulerian tour produced is then converted into a traveling salesman tour through the use of shortcuts, similar to the approach outlined in the minimum spanning tree heuristic in Section 2.3.1 Let LC denote the length of the tour generated by Christofides’ Heuristic, which we aim to prove.
T heorem 2.3.9 For all instances o f the TSP satisfying the triangle inequality, we have
The cost of the minimum spanning tree (MST) is represented as W* = W(T*), while W(M*) denotes the weight of the minimum weight matching, which is the total length of all edges in the optimal matching This relationship holds true under the assumption of the triangle inequality.
We already know that W ( T*) — L* It remains to show that W (M*) — 2L*
To optimize the minimum spanning tree, index the vertices of odd degree as i1, i2, , i2k based on their order in an optimal traveling salesman tour Evaluate two viable solutions for the minimum weight matching problem associated with these vertices The first solution, referred to as M1, comprises a selection of edges.
{i1, i2}, {i3, i4} , , {¿2k-1, i2k} The second matching, denoted M2, consists o f edges {i2, i3}, {i4, i5} , , {i2k, i }.
We clearly have W ( M*) — 2[W (M 1) + W(M 2)] The triangle inequality as sumption tells us that W ( M1) + W ( M2) — L*; see Figure 2.3 Hence W ( M*) —
As in the two previous heuristics, this bound is tight Consider the example depicted in Figure 2.4 for w hich L* = n while L C = n — 1 + n——1.
Local Search H e u r i s t i c s
The k-opt procedures, which are among the oldest and most widely utilized heuristics for solving the traveling salesman problem, belong to the broader category of local search techniques These methods, where k is greater than 2, are designed to enhance the efficiency of finding optimal routes.
FIGURE 2.3 The matching and the optimal traveling salesman tour
FIGURE 2.4 An example for Christofides’ algorithm with n = 1.
2.3 The T raveling S alesm an P roblem 31 as follows Given a traveling salesman tour through the set o f vertices V, say the sequence
A 2-exchange procedure in a traveling salesman tour involves replacing two existing edges with two new edges, thereby maintaining the integrity of the tour For example, by substituting the edges {u, iu2} and {v, iv2} with {u} and {iu2, iv2}, a new tour is generated This method effectively enhances the tour while ensuring it remains valid.
{i1 , i2 , iu\, iv\ , iv\ — 1 , • • • , iu2, iv2 , iv2 + 1 , • • • , in}.
An improving t -exchange is an t-exchange that results in a tour whose total length (cost) is smaller than the cost o f the original tour.
The £-opt procedure initiates with a random traveling salesman tour and progressively refines it through improving t-exchanges for t < k, resulting in tours of decreasing length This process concludes when no further improving t-exchanges are available for all t < k The length of the tour produced by a k-opt heuristic, where k > 2, is denoted as L OPT(k).
Recently, Chandra et al (1995) obtained interesting results on the worst-case performance o f the k-opt heuristic They show
T heorem 2.3.10 For all instances o f the TSP satisfying the triangle inequality we have j OPT(2)
In addition, there exists an infinitely large fa m ily o f TSP instances satisfying the triangle inequality assumption fo r which
They also provide a lower bound on the worst-case performance o f k-opt for all k > 3.
T heorem 2.3.11 There exists an infinitely large fa m ily o f TSP instances satisfying the triangle inequality assumption with
The findings suggest that k-opt heuristics may exhibit poor worst-case performance; however, numerous researchers and practitioners, including Golden and Stewart (1985), have documented their effectiveness in various applications.
This presents a critical dilemma: while worst-case analysis offers a strict assurance of a heuristic's performance, it is significantly influenced by specific pathological cases Therefore, the question arises: is there a more suitable metric to evaluate performance?
Worst-case analysis evaluates the effectiveness of a specific heuristic by examining its performance in extreme scenarios In the following chapter, we will explore whether this approach can also be applied to assess effectiveness in average or realistic examples.