A revised formulation, library and heuristic for a chemical tanker scheduling problem. (September 2021) - Ladage, Anurag; Baatar, Davaatseren; Krishnamoorthy, Mohan; Mahajan, Ashutosh
Highlights: We study a chemical tanker scheduling problem with time-windows and tank allocations. We introduce a compact MIP formulation with tighter linear relaxation. An instance generator based on real-world data. 200 instances for testing. Variation in the number of variables – 23, 115 to 497, 749. We introduce a linear programming based neighbourhood search heuristic. Abstract: We study a chemical tanker scheduling problem in which a multi-compartment chemical tanker picks up chemicals (within specific time windows) and delivers them to their destinations. Additional safety and ship balancing requirements related to the compartment storage need to be met. We refer to this problem as the single ship pick-up and delivery problem with pick-up time windows, tank allocations and changeovers (s-PDP-TWTAC). We propose a formulation for the s-PDP-TWTAC that is significantly smaller in size when compared to the existing approaches. Even though our formulation requires significantly lesser computational effort than others, it is still challenging to solve for large realistic networks. We propose a linear programming based neighbourhood search heuristic to find good solutions to these problems. We also describe an instance generator for creating random but realistic instances, and a library of instances that have been created for testing and benchmarking.