The Logic of Logistics

The concepts of convexity and supermodularity are important in the optimization and economics literature. These concepts have been widely applied in the analysis of a variety of supply chain models, from stochastic, multi-period inventory problems to pricing models. Hence, in this chapter, we provide a brief introduction to convexity and supermodularity, focusing on materials most relevant to our context. We also briefly introduce some concepts and results from discrete convex analysis, which interestingly is an elegant combination of both convexity and submodularity. For more details, readers are referred to the three excellent books Rockafellar (970) on convex analysis, Topkis (1998) on supermodularity, and Murota (2003) on discrete convex analysis.

Game theory provides a powerful mathematical framework for modeling and analyzing systems with multiple decision makers, referred to as players, with possibly conflicting objectives. A game studied in game theory consists of a set of players, a set of strategies (or moves) available to the players, and their payoffs (or utilities) for each combination of their strategies. Depending on whether the players can sign enforceable binding agreements, game theory consists of two branches: noncooperative game theory and cooperative game theory. Noncooperative game theory provides concepts and tools to study the behaviors of the players when they make their decisions independently. Cooperative game theory, on the other hand, assumes that it is possible for the players to sign enforceable binding agreements and provides concepts describing basic principles these binding agreements should follow. Both noncooperative game theory and cooperative game theory have been widely used in many disciplines, such as economics, political science, social science, as well as biology and computer science, among others. They have also received considerable attention in supply chain management literature in recent years. In this chapter, we provide a concise introduction to some of the key concepts and results that are most relevant in our context. We refer to Osborne (2003) and Myerson (1997) for both noncooperative game theory and cooperative game theory, Fudenberg and Tirole (1991) and Başar and Olsder (1999) for noncooperative game theory, Vives (2000) on oligopoly pricing from the perspective of noncooperative game theory, and Peleg and Sudhölter (2007) for cooperative game theory, respectively.

Since most complicated logistics problems, for example, the bin-packing problem and the traveling salesman problem, are \(\mathcal{N}\mathcal{P}\)-Hard, it is unlikely that polynomial-time algorithms will be developed for their optimal solutions. Consequently, a great deal of work has been devoted to the development and analyses of heuristics. In this chapter, we demonstrate one important tool, referred to as worst-case performance analysis, which establishes the maximum deviation from optimality that can occur for a given heuristic algorithm. We will characterize the worst-case performance of a variety of algorithms for the bin-packing problem and the traveling salesman problem. The results obtained here serve as important building blocks in the analysis of algorithms for vehicle routing problems.

Worst-case performance analysis is one method of characterizing the effectiveness of a heuristic. It provides a guarantee on the maximum relative difference between the solution generated by the heuristic and the optimal solution for any possible problem instance, even those that are not likely to appear in practice. Thus, a heuristic that works well in practice may have a weak worst-case performance, if, for example, it provides very bad solutions for one (or more) pathological instance(s).

An important method of assessing the effectiveness of any heuristic is to compare it to the value of a lower bound on the cost of an optimal solution. In many cases, this is not an easy task; constructing strong lower bounds on the optimal solution may be as difficult as solving the problem.

Production planning is also an area where difficult combinatorial problems appear in day-to-day logistics operations. In this chapter, we analyze problems related to lot sizing when demands are constant and known in advance. Lot sizing in this deterministic setting is essentially the problem of balancing the fixed costs of ordering with the costs of holding inventory. In this chapter, we look at several different models of deterministic lot sizing. First, we consider the most basic single-item model, the economic lot size model. Then we look at coordinating the ordering of several items with a warehouse of limited capacity. Finally, we look at a one-warehouse multiretailer system.

The inventory models considered so far are all deterministic in nature; demand is assumed to be known and either constant over the infinite horizon or varying over a finite horizon. In many logistics systems, however, such assumptions are not appropriate. Typically, demand is a random variable whose distribution may be known.

In this chapter, we analyze decentralized supply chain systems with independent retailers, each of which—facing uncertain demand—needs to decide its stock level and selling price in a single period. In Sect. 11.1, the retailers compete on prices for which noncooperative game theory is appropriate.

The inventory models discussed in Chap. 9 focus on characterizing the optimal replenishment policy for a single facility given some assumptions, such as lead time and yield, of its supplier. This of course emphasizes the need, in many cases, to develop direct relationships with suppliers.

For many manufacturing firms, the ability to match demand and supply is key to their success. Failure to do so could lead to loss of revenue, reduced service levels, negative impact on reputation, and decline in the company’s market share. Unfortunately, recent developments, such as intense market competition, product proliferation, and the increase in the number of products with a short life cycle, have created an environment where customer demand is volatile and unpredictable. In such an environment, traditional operations strategies such as building inventory, investing in capacity buffers, or increasing committed response time to consumers do not offer manufacturers a competitive advantage. Therefore, many manufacturers have started to adopt an operations strategy known as process flexibility to better respond to market changes without significantly increasing cost, inventory, or response time (see Simchi-Levi 2010).

In the last decade, many companies have recognized that important cost savings and improved service levels can be achieved by effectively integrating production plans, inventory control, and transportation policies throughout their supply chains. The focus of this chapter is on planning models that integrate decisions across the supply chain for companies that rely on third-party carriers. These models are motivated in part by the great development and growth of many competing transportation modes, mainly as a consequence of deregulation of the transportation industry. This has led to a significant decrease in transportation costs charged by third-party distributors and, therefore, to an ever-growing number of companies that rely on third-party carriers for the transportation of their goods.

One of the most important aspects of logistics is deciding where to locate new facilities such as retailers, warehouses, or factories. These strategic decisions are a crucial determinant of whether materials will flow efficiently through the distribution system.

A large part of many logistics systems involves the management of a fleet of vehicles used to serve warehouses, retailers, and/or customers. In order to control the costs of operating the fleet, a dispatcher must continuously make decisions on how much to load on each vehicle and where to send it. These types of problems fall under the general class of vehicle routing problems mentioned in Chap. 1.

In this chapter, we consider the capacitated vehicle routing problem with unequal demands (UCVRP). In this version of the problem, each customer i has a demand w _i and the capacity constraint stipulates that the total amount delivered by a single vehicle cannot exceed Q. We let Z _u ^∗ denote the optimal solution value of UCVRP, that is, the minimal total distance traveled by all vehicles.

A classical method, first suggested by Balinski and Quandt (1964), for solving the VRP with capacity and time-window constraints, is based on formulating the problem as a set-partitioning problem.

In this chapter, we present some of the issues involved in the practice of supply chain design and planning. These are issues that are often not dealt with in traditional operations research analyses. However, they are essential in transforming raw data and problem characteristics into modeling assumptions, input data, and decisions.

We now turn our attention to a case study in transportation logistics. We highlight particular issues that arise when implementing an optimization algorithm in a real-life routing situation. The case concerns the routing and scheduling of school buses in the five boroughs of New York City.