An iterative solution approach to capacitated two-stage time minimization transportation problem with destination-stage demand specified

Because of realistic necessity for timely satisfying destination-stage demand, capacitated two-stage time minimization transportation problem with destination-stage demand specified (C2SD) is crucial and important optimization problem with no research report in literature due to its super intractability. In this paper, by creating C2SD’s mathematical model named C2SDM (i.e. the main model systematically formulating C2SD problem) along with auxiliary models and constructing network, C2SD is reduced to a series of search for feasible flow in the constructed network, and consequently four iterative algorithms, with two derived respectively from other two by applying binary search, are developed to solve C2SD. It is proved that the optimum solution is found for C2SD by each of the four algorithms in a polynomial time. Owing to sufficient exploitation of the network structure of C2SD, the proposed algorithms exhibit high computational efficiency and avoid memory overflow. They are also easy to implement computationally and can be readily extended to capacitated multistage time minimization transportation problems with destination-stage demand specified. Distinct size examples are presented to showcase the application value and practical performance difference of the four algorithms compared to generic solver LINGO applied to C2SDM model, and the causes for incurring the performance difference are analyzed. Computation experiments on different size instances produced at random are conducted to further validate the practical performance of the four iterative algorithms compared with LINGO. It is validated that all the four algorithms overwhelmingly excel LINGO in solving quality and rival LINGO in computation time when applied to C2SD instances, successfully overcoming the defect of LINGO with poor optimization effect. It is indicated that the developed four algorithms are robust and efficient exact solution approach to C2SD, and they are able to serve as a powerful tool to tackle other relevant complex optimization problems.