Big Is Green, Procompetitive, and Profitable: The Economics of Route Consolidation

doi:10.21203/rs.3.rs-4096019/v1

Download PDF

Research Article

Big Is Green, Procompetitive, and Profitable: The Economics of Route Consolidation

https://doi.org/10.21203/rs.3.rs-4096019/v1

This work is licensed under a CC BY 4.0 License

You are reading this latest preprint version

The Travelling Salesman Problem and its cousin, the Vehicle Routing Problem, are typically studied in the field of Operations as a problem of optimization. In this paper, we show how to generalize the framework to handle any economic optimization problem using the idea of opportunity cost to elicit preferences. We prove that an optimum exists and then use stochastic search to estimate it for a realistic application involving actual drive times, multiple drivers, and overtime in Austin Texas. We find the benefits of route consolidation are large enough to offset potential anticompetitive effects for reasonable demand elasticities, and that the reduction in delivery miles results in lower costs, less pollution, and fewer accidents, injuries, and deaths. But unlike classic pollution externalities, most of benefits of route consolidation are internal to the merging parties, so they would be realized absent government intervention.

ESG

Competition

Merger Effects

Merger Efficiencies

Economic Tradeoffs

Environmental Externalities

Travelling Salesman Problem

Vehicle Routing Problem

In 2020, American Airlines and JetBlue announced an alliance¹ which made them partners at three New York area airports and in Boston. They agreed to sell seats on one another’s flights along certain routes, pool airport slots, and coordinate schedules. The resulting coordination would have lowered costs, increased load factors, and reduced pollution. The U.S. Transportation Department approved the alliance 10 days before the end of the Trump administration. But soon after President Biden took office, the Justice Department sued to block the deal.² In 2023, the partnership was struck down by a Federal Judge.³

At a 2022 oversight hearing, Chair Lina Khan of the U.S. Federal Trade Commission (FTC) testified that that environmental, social, and governance (ESG) benefits would not rescue an otherwise anticompetitive merger.⁴ But other jurisdictions, like the Netherlands, are updating their antitrust rules in pursuit of such goals.⁵ More generally, the OECD (2021) has suggested that environmental benefits may be counted under a consumer welfare standard:

There are also agreements that, albeit anticompetitive in a first analysis, may be considered to … outweigh the competition restriction or otherwise meet the requirement of providing benefits to the consumers.

Unfortunately, most ESG measures are noisy (e.g., Berg et al., 2020), so even for a jurisdiction that wants to take them into account, it can be difficult to do so.

For route consolidation, however, ESG benefits follow from the reduction in delivery miles. Not only does this allow computation of the benefits of pollution, accident, and injury reductions, but it also allows us to compute the ESG/competition tradeoff in the context of a model of route consolidation where e.g., independent stores with separate delivery systems move to an online electronic marketplace with a unified fulfillment network.

We find that economies of route consolidation are large enough to offset anticompetitive effects for reasonable demand elasticities, and that the reduction in miles driven results in lower costs, less pollution, and fewer accidents, injuries, and deaths. Moreover, the model allows us to calculate the internal as well as the external benefits of route consolidation. Unlike classic pollution externalities, most of the gains to route consolidation accrue to the merging parties. In other words, for companies with unified route delivery, being green is privately profitable, without government intervention.

The Vehicle Routing Problem

The well-known “Traveling Salesman Problem” (TSP), and its cousin the “Vehicle Routing Problem” (VRP), are classes of discrete optimization problems for which it is not possible to find the global optimum in polynomial time. Heuristics, largely developed in the field of Operations, have been successfully used to approximate the optimum (for a review see Braekers et al., 2016). For an animated demo of some of the popular techniques see link.⁶

The simplest is the “Nearest-Neighbor” heuristic. It starts at one point (delivery location) and connects with the closest un-visited point. It repeats until every point has been visited, and then returns to the starting point. On average, it is inefficient because the last step connecting the endpoint to the starting point is inefficiently long.

The “Nearest-Insertion” heuristic begins with two points, then repeatedly finds the point not already in the “tour” (connecting the points) that is closest to any point in the tour. Although this avoids the last-step problem of the Nearest Neighbor, the Nearest-Insertion is still suboptimal as it looks only one-step ahead, and usually gets “stuck” at a local minimum.

The Lin-Kernighan (1973) and Lin–Kernighan–Helsgaun (LKH) (Helsgaun, 2000) heuristics improve upon the “nearest insertion” heuristic by searching among neighborhoods of points for a shorter route and, upon finding one, repeats the process for that new route, which gets much closer to a global minimum. In this paper, we generalize the LKH algorithm using the idea of opportunity cost to minimize the total costs of a realistic routing problem with multiple drivers, territories, and overtime to worry about. In Appendix A, we show that, under certain conditions, there exists an insertion order that finds the minimum total cost of a route, and then use a stochastic search (Powell, 2023) to find it.

Eliciting Soft Costs from Tradeoffs

Hard costs like distance are relatively simple to compute and minimize. But in most applications, intangible costs are just as important. In this section, we show how to elicit intangible costs from a manager using opportunity cost and then make them part of the route optimization. Note that the same methodology could be used to quantify the costs of C02 pollution from preferences of policy makers.

For example, late time has the potential to alienate customers, but it is difficult to quantify the costs of late time so they can be minimized. In this section, we show how to elicit these costs by presenting a manager with a series of tradeoffs. Imagine the following conversation between Operations (OPS) and Management (MGT).

OPS: “How much would you be willing to spend in incremental deployment costs to be on-time vs. 30 minutes late?”

MGT: “Maybe $30 per delivery.”

OPS: “OK, let’s run it and see what happens.”

MGT: “That looks pretty good, but I still have too much late time.”

OPS: “OK, we will set the cost of being late so that it hits $60 at 30 minutes and run it again.”

MGT: “Now, on-time arrivals are great, but I have too much overtime.”

OPS: “Let’s try $45 at 30 minutes.”

MGT: “That looks good. We are a few minutes late and have a bit of overtime, but the plan looks good.”

By simulating various scenarios, Operations can present Management with a series of tradeoffs and turn subjective concerns about losing customers into explicit costs that can be minimized. The result is a generalized system that can minimize total costs, both hard and soft (Powell, 2022).

Theory

To illustrate the problem in its simplest terms, consider a two-dimensional route delivery example with n points uniformly distributed over a unit square. Beardwood et al. (1959) showed that the average distance per delivery for an optimal route of n uniformly distributed locations on a unit square converges to ß/$\sqrt{n}$ for some finite ß. In other words, a quadrupling of density, like that brought about by a merger of four delivery companies, would result in a 50% reduction in distance traveled, provided the truck had the capacity to deliver the packages. But with capacity constraints problem becomes more complex.

We illustrate some of this complexity in Fig. 1 by considering different truck capacities delivering to n = 100 randomly distributed points on a unit square. In the left column, we compute distance for a truck that can carry only one package (k = 1), out from a central hub and back again. This out-and-back benchmark can be used as a proxy for the high costs of individual shopping trips relative to home delivery (Brown & Griffida, 2014; Astashkina et al., 2019; Houde et al., 2021). Analytically, out-and-back total distance travelled can be computed as 𝐷₁(𝑛) = 𝛼𝑛, 𝛼 ≈ 0.765, where n is the number of deliveries.

In the far-right column, we calculate the optimal route for a truck that can deliver all packages in a single day with no driver breaks. For this unconstrained case (k=∞), distance travelled is 90% shorter than the out-and-back benchmark, where 𝐷_∞(𝑛) ≈ 𝛽 𝑛; 𝛽 ≈ 0.73. In the second row of the table, we see that these savings are not sensitive to the choice of a Taxicab vs. Euclidean distance metric.

In the middle column, we calculate the intermediate case with nine trucks, each serving a single neighborhood “cluster.” Formally, imagine dividing a square area into (m x m) neighborhoods with average truck capacity of k ≈ n/m²=𝛼 m²+m D_∞(n/m²) = (𝛼/k) n + D_∞(k) $\sqrt{n/k}$. Using the same delivery locations, we see that the distance travelled is 84% shorter than the out-and-back benchmark.

Application: Austin, TX

Whether such savings would extend to more realistic Vehicle Routing Problems, with constraints on truck capacities, driver times, and delivery windows is an open question. We answer it by computing optimal routes for randomly generated delivery locations in Austin Texas MSA, using actual street-level expected travel times for two thousand, five thousand, and ten thousand daily deliveries.

We start by simulating random delivery distributions across the Austin MSA, subject to the constraint that each location be a valid delivery address. Then, we cluster those locations using a geographical partitioning algorithm (Carlsson, 2021) and compute optimal routes within each cluster. K-Means geographic clusters are computed subject to the restriction that a zip code cannot lie in more than one cluster.

The clustering algorithm is illustrated in Table 2 for 2500 daily deliveries. Inputs to the algorithm are a collection of locations, a GIS Distance Correlation Matrix (DCM) that provides the travel time between any two locations in the corpus, and a desired number of clusters, K, chosen to satisfy the constraints on driver time, delivery windows, and truck capacity.

The algorithm begins with seed locations that start the formation of the clusters. These can be randomly placed, evenly spaced, or follow some heuristic if other bits of information are to be considered, such as census data block or zip code centroids. Formally, we divide n observations into k-mean clusters in which each observation belongs to the cluster with the nearest mean (center). Such k-means clustering minimizes within-cluster variance (squared Euclidian distance within a cluster).

Then, for each point in the corpus, the closest cluster is determined without violating restrictions, and that point is placed into that cluster. The minimum point in each cluster, according to the sum of the distances of that point to every other point in the cluster, is computed and updated with each point added. This point becomes the seed location for each respective cluster and the algorithm repeats until no new seed locations are determined or a maximum number of iterations has been reached.

After we compute geographical clusters, we assign vehicles to the various clusters and optimize routes. The map to the right shows the clusters and the street-level routes that result. The bottom panel of Table 2 is a sector with a single van route for a density of 2,500 deliveries in Austin per day. To simplify the analysis, we assume that delivery vans have sufficient capacity to make the requisite deliveries to within each neighborhood.

We show the economies of route consolidation in Table 3. In the top panel of the table, we plot the miles/delivery vs. the number of firms. A single firm delivering 2,500 packages (blue line) across an area the size of Austin has: (i) only one-third the miles/delivery as ten firms delivering 2,500 packages (blue line); and (ii) approximately the same miles/delivery as four independent entities making 10,000 deliveries across the same area (grey line).

In the bottom panel of the table, we plot the total distance vs. the number of deliveries. We show: (i) a quadrupling of the delivery density results in a 47% reduction in the miles per delivery, very close to the predicted 50% savings of Beardwood et al.’s (1959) simple model. This translates into huge cost savings, less pollution, and fewer accidents, injuries, and deaths. For an estimated 5,000 daily deliveries in Austin (1.825M/year), a single coordinated delivery enterprise vs. four independent delivery companies results in 203,000 less delivery miles annually.

Table 4

CONSOLIDATING FOUR ROUTES INTO ONE
	ASSUMPTIONS	AUSTIN	US
Deliveries		1.825M	5B
Vehicle Costs	$0.585/Mile	$127K	$348M
Driver Costs	$49,110/Driver year	$148K	$404M
Accidents/Injuries/ Deaths per mile	296/84/1.11	0.429/0.122/.002	1,178/476/6
CO2 Emissions	.00032 MT/Mile	66	180,000

In Table 4, we suppose that a firm like Amazon has consolidated the equivalent of four routes, e.g., by convincing groups of stores to use Amazon’s fulfillment services instead of independent alternatives. We start by assuming 5,000 daily deliveries for Austin as the average number of Amazon deliveries for a city of Austin’s size and quantify the expected reduction in the number of accident/injury/deaths using national rates (296/84/1.11) per 100M miles driven from the National Highway Traffic Safety Administration (NHTSA, 2021, link). Pollution statistics are computed in Appendix B, where we assume that the average freight truck in the U.S. emits 161.8 grams of CO₂ per ton-mile (Environmental Defense Fund, 2015, link).

Extrapolating from Austin to the rest of the US yields annual savings of 550M delivery miles, emitting 180,000 fewer metric tons of CO2 emissions, with 1,178 fewer accidents, 476 fewer injuries, and 6 fewer deaths, in addition to savings of $348M and $404M in vehicle and driver costs.

Economies of Density vs. Loss in Competition

The big economies of the previous section must be weighed against the loss in competition by asking whether stores (and their customers) would be better off had Amazon not consolidated the four routes. On the one hand, stores are attracted by Amazon’s delivery efficiencies but on the other, they are worried that consolidation might increase the price of delivery services. This hypothetical is designed to illustrate the loss of competition vs. economies of density tradeoff.⁷

To measure the potential loss in delivery competition, we assume that the four consolidated routes belong to four symmetric firms competing in the delivery market with one another. We measure the loss in competition by assuming that all of Amazon’s 21% share of parcel delivery (Pitney Bowes, 2020, link) came from consolidating the four independent firms, who then compete with UPS, FEDEX, and USPS.

To do the benefit-cost analysis, we use a simple Cournot model of competition, and ask whether the lower costs associated with a reduction in miles driven would outweigh the loss in competition. This is equivalent to asking whether the “compensating marginal cost reduction” (CMCR) necessary to offset the anticompetitive effects (Froeb and Werden, 1996) is smaller than the predicted marginal cost reduction. Table 2 illustrates computes the CMCR as a function of the change in concentration and elasticity of delivery demand.

Table 5

% ∆MC that Restores Pre-Merger Price
	Market Demand Elasticity
∆HHI	-1	-2	-3
100	7.6	3.7	2.4
500	18.8	8.6	5.6
1000	28.8	12.6	8.1
2500	54.7	21.5	13.4
5000	100	33.3	20

Suppose that the absolute value of the market elasticity of demand for last mile delivery services is -1 (first column in table above). For our implied change in concentration of 330, it would take at most an 18% reduction in MC to prevent a price increase. Based on our simulations in Austin, the MC reduction of route consolidation is way above that, at 47%. In other words, the economies of route consolidation would lead to a price decrease, not a price increase.

There is pressure from consumers and investors to pursue sustainable and ESG goals. However, because ESG measures are “…prone to bias, mismeasurement and public-relations peacocking” (Buttonwood, 2023), this is hard to do. And to the extent that “green” firms can be identified, they tend to be services firms. But investing in service firms tends to be “counterproductive” as their environmental impact barely changes (Hartzmark and Shu, 2022).

In this paper, we show how to use a model-based approach to measure the benefits and costs of various counterfactuals without the handwaving often associated with ESG. When we do this, we find that route consolidation not only reduces costs by reducing miles driven, but also reduces traffic, which directly reduces pollution, accidents, injuries and deaths. Most of these costs are internal (vehicle and driver costs) or capitalized into insurance rates. So, unlike classical externalities, these pollution reductions are privately profitable.

Author Contribution

All authors worked on the manuscript as it evolved over the course of about five years.

Astashkina, Ekaterina and Belavina, Elena and Marinesi, Simone, The Environmental Impact of the Advent of Online Grocery Retailing (March 10, 2019). Available at SSRN: https://ssrn.com/abstract=3358664 or http://dx.doi.org/10.2139/ssrn.3358664
Beardwood, J.; Halton, J.H.; Hammersley, J.M. (October 1959), "The Shortest Path Through Many Points", Proceedings of the Cambridge Philosophical Society, 55 (4): 299–327.
Berg, Florian, Julian F. Koelbel, Roberto Rigobon (November 2022), Aggregate Confusion: The Divergence of ESG Ratings. Review of Finance, Volume 26, Issue 6, Pages 1315–1344, https://doi.org/10.1093/rof/rfac033
Kris Braekers, Katrien Ramaekers, Inneke Van Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering, 99 (2016) 300–313.
Brown, J. R., & Guiffrida, A. L. (2014). Carbon emissions comparison of last mile delivery versus customer pickup. International Journal of Logistics Research and Applications, 17(6), 503-521.
Carlsson, John Gunnar and Liu, Sheng and Salari, Nooshin and Yu, Han, Provably Good Region Partitioning for On-Time Last-Mile Delivery (September 1, 2021). Rotman School of Management Working Paper No. 3915544, Available at SSRN: https://ssrn.com/abstract=3915544 or http://dx.doi.org/10.2139/ssrn.3915544
Buttonwood, “The anti-ESG Industry is taking investors for a ride,” Economist (March 4, 2023), Available at https://www.economist.com/finance-and-economics/2023/03/02/the-anti-esg-industry-is-taking-investors-for-a-ride.
Froeb, Luke M. and Gregory J. Werden, A Robust Test for Consumer Welfare Enhancing Mergers Among Sellers of a Homogeneous Product, 58 ECON. LETTERS, 267-269 (1998).
Hartzmark, Samuel M. and Shue, Kelly, Counterproductive Sustainable Investing: The Impact Elasticity of Brown and Green Firms (November 1, 2022). Available at SSRN: https://ssrn.com/abstract=4359282
Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European journal of operational research, 126(1), 106-130.
Hoos, Holger H. and Thomas Stützle (2004), Stochastic Local Search Foundations and Applications, Morgan Kaufmann.
Houde, Jean-François, Peter Newberry, and Katja Seim, Economies of Density in E-Commerce: A Study of Amazon’s Fulfillment Center Network, NBER Working Paper No. 23361 (April 2017, Revised May 2021).
Kalantari, B., Hill, A. V., & Arora, S. R. (1985). An algorithm for the traveling salesman problem with pickup and delivery customers. European Journal of Operational Research, 22(3), 377-386.
Liao, E., & Liu, C. (2018). A hierarchical algorithm based on density peaks clustering and ant colony optimization for traveling salesman problem. IEEE Access, 6, 38921-38933.
Le Ny, J., Frazzoli, E., & Feron, E. (2007, December). The curvature-constrained traveling salesman problem for high point densities. In 2007 46th IEEE Conference on Decision and Control (pp. 5985-5990). IEEE.
Lin, Shen; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research. 21 (2): 498–516.
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
OECD (2021), Environmental considerations in competition enforcement, OECD Competition Committee Discussion Paper, https://www.oecd.org/daf/competition/environmental-considerations-in-competitionenforcement.htm
Powell, G.E, Lane, M.T., US Patent No 11,315,053, “Systems and Methods for Optimizing Complex Systems,” (priority date February 13, 2020, granted April 26, 2022).
Savelsbergh, M. W., & Sol, M. (1995). The general pickup and delivery problem. Transportation science, 29(1), 17-29.
Yang, Z., Xiao, M. Q., Ge, Y. W., Feng, D. L., Zhang, L., Song, H. F., & Tang, X. L. (2018). A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods. European Journal of Operational Research, 265(1), 65-80.

Doug Cameron and Alison Sider, American Targets New York Expansion With JetBlue Pact, Wall St Journal (July 16, 2020), link.
Edward Russell, JetBlue May Need to Give Up American Airlines Alliance to Win Spirit Merger Approval, Airline Weekly (Feb 13, 2023), link.
Rennison, Joe and Nirah Choksi, “JetBlue-American Partnership Struck Down by Federal Judge, NY Times (May 19, 2023), available at https://www.nytimes.com/2023/05/19/business/jetblue-american-northeast-alliance-justice-department.html.
Logan Breed, Ilana Kattan, ESG Initiatives: No Defense Under US Antitrust Laws, Hogan Lovells Press Relase (September 26, 2022)
Netherlands Authority for Consumers and Markets, Many arrangements within production chains regarding sustainable agriculture are allowed
(September 7, 2022), link.
A visual demonstration of common heuristics is available at 11 Animated Algorithms for the Traveling Salesman Problem
Houde et al. (2021) suggest that such delivery efficiencies are dependent on or “specific” to Amazon’s vertical integration of fulfillment with its electronic marketplace.

Tables 1 to 3 are available in the Supplementary Files section.

Competing interest reported. The topic of the paper is delivery economies of scale, and we use Amazon as an example. Amazon supported this project but did not give us any data, nor have any say in how we did the research or what we published. We acknowledge the support in the article footnote: "We thank Sam Clyde and Jack Underwood for fabulous RA work; and acknowledge support from Amazon for this project. The opinions expressed in this paper are solely those of the authors."

Download PDF

Editorial decision: Revision requested
10 Jun, 2024
Submission checks completed at journal
14 Mar, 2024
Editor assigned by journal
14 Mar, 2024
First submitted to journal
13 Mar, 2024

You are reading this latest preprint version

Big Is Green, Procompetitive, and Profitable: The Economics of Route Consolidation

Status:

Version 1

Abstract

I. Introduction: ESG vs. Competition

II. Methodology: Economics of the Vehicle Routing Problem

III. Economies of Route Consolidation

IV. Conclusion: ESG without handwaving

Declarations

References

Footnotes

Tables

Additional Declarations

Supplementary Files

Status:

Version 1