Integer programming models for unidirectional and bidirectional cyclic load-dependent routing problems

Purpose Vehicle load is a critical factor that impacts route selection within logistic networks. This study aims to compare two different strategies for generating routes in a cyclic load-dependent traveling salesman problem. Design/methodology/approach The study introduces novel load-dependent cyclic routing strategies and propose two new problems to model them: The unidirectional and bidirectional variants of the cyclic load-dependent traveling salesman problem. Three mathematical formulations are proposed for the problems using integer linear programming. Two formulations, for both variants of the problem, use the so-called MTZ constraints while the third one for the bidirectional variant is based on an arc-network. To evaluate the performance of the proposed strategies, the study uses three sets of instances: benchmarks from the literature, realistic instances and randomly generated instances. Findings The study shows that the bidirectional strategy is strictly better than the unidirectional one in instances with unitary distances and demands. For general-distance and general-demand instances, computational results show that the bidirectional strategy obtains better solutions than the unidirectional one in most cases. Originality/value The proposed problems are original despite being variants of cyclic inventory routing problems. The load on the vehicle is often neglected in operational research literature. The bidirectional strategy in the context of cyclic problems is original. While not extremely complex, the theoretical results on unitary distance and unitary demand instances are new.