Global distribution center placement

Where should a company put its warehouses to stay close to the most customers? I compared three ways of answering that across the world's 1,000 largest cities, measured distance the way freight actually moves, by road and by sea, and added the limits real warehouses have: capacity and running cost.

Cities

1,000

Countries

129

Road and sea, k=5

1,968 km

Solve time

< 1 s

The problem

Pick k cities to host distribution centers so that customers, weighted by how much they buy, are as close as possible to their nearest center. Operations research calls this the p-median problem. It's easy to state and hard to solve exactly: choosing 5 sites from 1,000 cities has more than 8 trillion combinations.

A planner can weight demand by population or by purchasing power, penalize sites in countries with weak logistics, force specific cities in, cap how much one center can handle, and charge each site a running cost. GDP per person, logistics scores (the World Bank's Logistics Performance Index) and price levels come from the World Bank for 126 of the 129 countries; the rest use the median of their income group.

Measuring distance like freight

A straight line over the globe happily drives a truck across the Atlantic. Freight can't, so every pair of cities gets a freight distance:

• Same landmass: the straight line times a road detour factor for each country, from published estimates of how much longer roads are than straight lines (1.20 in the United States, 1.31 in India, 1.65 in France).
• Different landmass: road to the nearest coast, then the shortest sea route, then road again. Sea routes run on a half-degree ocean grid with the Suez and Panama canals and the narrow straits added, and the frozen Arctic closed.

The sea routes come out close to the distances shipping lines quote: about 19,500 km from Rotterdam to Shanghai through Suez and 6,250 km from New York to Rotterdam. Landmasses follow real road links: the Channel Tunnel joins Britain to Europe, while the Darien Gap separates Central and South America and the closed Korean border makes South Korea an island.

Three approaches

1. K-Means: cluster cities in 3D space, then place each center at the city nearest its cluster's middle. Very fast, but it optimizes squared straight-line distance rather than the distance we care about.
2. K-Medoids: work directly with the distance matrix. Start with a reasonable set of centers, then keep moving any center to any other city if that lowers total distance, until no move helps.
3. Mixed-integer programming (MILP), seeded by K-Medoids: a solver that proves its answer is optimal, but only over a list of candidate sites. Instead of the most populous cities, the list comes from K-Medoids: its sites for nearby values of k, each site's nearest neighbours, and the biggest cities, about 230 to 480 candidates in all.

Results

Average distance from a customer to their nearest center, in km. Lower is better. Selected rows; the full table of 12 cases is in the repository.

Freight distances are about a quarter longer, and the map changes. With 5 centers and population weighting, the average trip grows from 1,560 km to 1,968 km. The straight-line answer puts sites in São Paulo, Alexandria, Gwalior, Macheng and Birmingham. By road and sea they move to Lu'an in China, Raipur in India, Konya in Turkey, New Orleans and Libreville in Gabon. Konya serves Europe and the Middle East by road, Libreville serves Africa and, by sea, eastern South America, and New Orleans covers North America and the Pacific coast of South America.

The seeded MILP mostly confirms K-Medoids, and sometimes beats it. In 10 of the 12 cases it proved the K-Medoids answer was the best on its candidate list. In the other two it found better ones, most clearly with purchasing-power weighting and 5 centers (1,739 km, 1.8% better). Each solve takes 25 to 90 seconds; K-Medoids takes under one. By contrast, a MILP limited to the 50 most populous cities lost to K-Medoids at every size (1,609 vs 1,560 km with 5 centers, straight line), because the best sites are often smaller, well-placed cities.

Capacity and running costs

Real centers have limits. With 5 centers and no limit, the center in China serves 51% of all demand. Capping each center changes the network:

At 25%, China gets two centers, and Europe, the Middle East and much of Africa share one in western Turkey. Here the MILP earns its keep: the capacity-aware search finds 2,195 km, and the MILP, seeded with that answer, proves 2,170 km is optimal on its candidate list (it may split a city between two centers, which the search doesn't).

Running costs let the model decide how many centers to open. Each site's cost is set at US prices and scaled by its country's price level, so a center in India costs about a quarter of one in the United States. The cost is expressed as distance: at 400 km, opening a center is worth it only if it cuts the average trip by more than 400 km times the site's price level.

Price level is a blunt stand-in for running cost. On its own it pulls sites toward the cheapest economies, including some no company would build in. Combining it with the logistics penalty moves them toward places like Memphis and Kraków.

What I'd do next

• Price each mode. A kilometre by ship costs far less than a kilometre by truck. Weighting road and sea separately would turn distance into transport cost.
• Route real roads for the busiest lanes with an open road network, instead of detour factors.
• Use real demand and site costs. Sales data instead of population, and rents and wages instead of national price levels.