Given a set P of n points with their pairwise distances, the traveling salesman problem (TSP) asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the l1 distance. The fixed-parameter algorithm for the Rectilinear TSP presented in [1] and its implementation are available on this page. The algorithm has a worst case time complexity of O(nh7^h) where h ≤ n denotes the number of horizontal lines containing the points of P.

[1] Hadrien Cambazard, Nicolas Catusse, Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane. European Journal of Operational Research 270(2): 419-429 (2018)

The order picking problem is a closely related problem where the products or orders have to be collected in a rectangular warehouse in the minimum amount of time. It is currently a major bottleneck in supply-chain because of its cost in time and labor force. The problem can be solved very efficiently with the same algorithm [2] that is also available for download on this page.

[2] Lucie Pansart, Nicolas Catusse, Hadrien Cambazard, Exact algorithms for the order picking problem. Computers & OR 100: 117-127 (2018)

Note that the softwares are distributed for research purpose only and the license prevents any commercial use: License