A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing. (December 2019)

• Record Type: Journal Article
• Authors: Li, Chongshou; Gong, Lijun; Luo, Zhixing; Lim, Andrew
• Is Part Of: Omega. Volume 89(2019)
• Page Start: 71
• Page End: 91
• Publication Date: 2019-12
• Subjects: Vehicle routing -- Pickup and delivery -- Branch-price-and-cut -- Exact algorithm; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2018.09.014
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: Introduced a new variant of the multi-vehicle multi-commodity pickup and delivery problem. Implemented a branch-and-price-and-cut algorithm. Proposed an ad-hoc label-setting algorithm to solve the pricing problem. Generated test instances and benchmark results for future researchers of the problem. Solved a new real-world problem via efficient algorithms. Abstract: We investigate a real-world product distribution problem faced by a fast fashion retailer in Singapore. It is a generalization of the multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) proposed by Hernández-Pérez and Salazar-González [15]. Each weekend the retailer forecasts the demand of each product for the next week. To ensure the inventory level equal to the forecast, the retailer schedules a fleet of vehicles to pick up or deliver products from/to each store at the beginning of each week. Shipping products from a store in surplus to another store in shortage is encouraged. For products that cannot be balanced among the stores, they are either picked up or delivered from/to the warehouse, which incurs a handling cost for each unit. The objective is to minimize the total travel distance as well as the total handling cost at the warehouse. To solve this problem, we propose a branch-and-price-and-cut algorithm based on a strong set-partitioning model, where an ad-hoc label-setting algorithm is designed to solve the pricing problem. The algorithm is tested on a set of instances generated according to a real-world database from the retailer and the m-PDTSP benchmark instances. Computational results show that our algorithm can optimally solve instances with 20 stores and over 100 products in one hour computational time. Moreover, it successfully solves several open m-PDTSP benchmark instances to optimality.