Territorial design for customers with demand frequency

• DOI: 10.1016/j.ejor.2023.01.016
• Publication Date: 2023-01-17T10:43:28Z
• Authors: Lu Zhen; Jiajing Gao; Zheyi Tan; Gilbert Laporte; Roberto Baldacci
• Keywords: OR in service industries; Column generation; 05 social sciences; 0211 other engineering and technologies; /dk/atira/pure/subjectarea/asjc/2200/2209; name=Industrial and Manufacturing Engineering; 02 engineering and technology; Set partitioning; /dk/atira/pure/subjectarea/asjc/1800/1803; name=Management Science and Operations Research; Territorial design problem; 0502 economics and business; /dk/atira/pure/subjectarea/asjc/1700/1700; name=General Computer Science; /dk/atira/pure/subjectarea/asjc/1800/1802; name=Information Systems and Management; Column generation; OR in service industries; Set partitioning; Territorial design problem; /dk/atira/pure/subjectarea/asjc/2600/2611; name=Modelling and Simulation

Territorial design is an important long-term decision for urban delivery service companies, in contexts where customers are partitioned into districts. This study focuses on a territorial design problem given the demand frequency of each customer, i.e., the estimated percentage of days with demand, over the planning horizon. This study formulates a set partitioning model and designs a column generation based algorithm to solve the problem. The algorithm decomposes the original problem into a restricted master problem (RMP) and a series of pricing problems (PPs), each limited to one district. A dynamic programming based method is designed to solve the PPs efficiently. To further accelerate the solution processes of the PPs and of the RMP, some tailored strategies are also embedded within the algorithm. Numerical experiments are conducted to validate the contributions of the dynamic programming and of the acceleration strategies. Some tests based on real-world cases are also performed in order to derive some managerial insights to support the practitioners’ decisions on service territory design.