A stabilized branch-and-price-and-cut algorithm for the waste transportation problem with split transportation. (April 2023)

• Record Type: Journal Article
• Authors: Zhang, Li; Liu, Zhongshan; Shan, Wenxuan; Yu, Bin
• Is Part Of: Computers & industrial engineering. Volume 178(2023)
• Publication Date: 2023-04
• Subjects: Waste transportation -- Split transportation -- Branch-and-price-and-cut algorithm -- Stabilized column generation; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2023.109143
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The vehicle routing problem for the waste transportation problem with split transportation and inter-depot is studied. The stabilized column generation is proposed to speed up the convergence speed of the algorithm. The proposed stabilized branch-and-price-and-cut algorithm is efficient in providing high-quality solutions. The split transportation can achieve lower total travel time and help operators save operational cost, compared with the case without split transportation. The variance of demand distribution, number of commodities, and trailer capacity would affect the effect of split transportation. Abstract: In the context of waste classification, different categories of waste are collected and stored separately in each collection location, which makes the split transportation implement readily in the waste transportation problem. The split transportation refers to that trailers are allowed to visit each location several times to transport different categories of waste from collection locations to transfer stations. Since split transportation relaxes the basic assumption that each collection locationshould be visited exactly once, it would lead to flexible combinations of routes and help waste transportation departments or companies save on operational costs. In this paper, we present a novel waste transportation problem that extends the traditional waste transportation problem by introducing the concept of split transportation. We develop a mixed integer programming formulation and a branch-and-price-and-cut algorithm on an extended network to solve the investigated problem. The extended network simplifies the pricing subproblem, but renders high degeneration in column generation. Then, the stabilized technique is devised to speed up the convergence speed of the proposed algorithm. The efficiency of the proposed algorithm is tested on a real-world instance and a set of benchmark instances. Then, we discuss the impact of split transporation, demand intervals, and trailer capacity to give managerial insights for waste transportation departments or companies.