Pareto-improving contracts for express package delivery services

We address the problem of an express package delivery company in structuring a long-term customer contract whose terms may include prices that differ by day-of-week and by speed-of-service. The company traditionally offered speed-of-service pricing to its customers, but without day-of-week differentiation, resulting in customer demands with considerable day-of-week seasonality. The package delivery company hoped that using day-of-week and speed-of-service price differentiation for contract customers would induce these customers to adjust their demands to become counter-cyclical to the non-contract demand. Although this usually cannot be achieved by pricing alone, we devise an approach that utilizes day-of-week and speed-of-service pricing as an element of a Pareto-improving contract. The contract provides the lowest-cost arrangement for the package delivery company while ensuring that the customer is at least as well off as he would have been under the existing pricing structure. The contract pricing smooths the package delivery company's demand and reduces peak requirements for transport capacity. The latter helps to decrease capital costs, which may allow a further price reduction for the customer. We formulate the pricing problem as a biconvex optimization model, and present a methodology for designing the contract and numerical examples that illustrate the achievable savings.