2018/05/03 by Christoph Hansknecht, Hansknecht, Christoph, Imke Joormann +3 · 5 citations
Engineering · #Vehicle Routing Optimization Methods #Optimization and Packing Problems #Assembly Line Balancing Optimization
paper · pdf · doi:10.48550/arxiv.1805.01415
We consider the time-dependent traveling salesman problem (TDTSP), a\ngeneralization of the asymmetric traveling salesman problem (ATSP) to\nincorporate time-dependent cost functions. In our model, the costs of an arc\ncan change arbitrarily over time (and do not only dependent on the position in\nthe tour). The TDTSP turns out to be structurally more difficult than the TSP.\nWe prove it is NP-hard and APX-hard even if a generalized version of the\ntriangle inequality is satisfied. In particular, we show that even the\ncomputation of one-trees becomes intractable in the case of time-dependent\ncosts. We derive two IP formulations of the TDTSP based on time-expansion and\npropose different pricing algorithms to handle the significantly in- creased\nproblem size. We introduce multiple families of cutting planes for the TDTSP as\nwell as different LP-based primal heuristics, a propaga- tion method and a\nbranching rule. We conduct computational experiments to evaluate the\neffectiveness of our approaches on randomly generated in- stances. We are able\nto decrease the optimality gap remaining after one hour of computations to\nabout six percent, compared to a gap of more than forty percent obtained by an\noff-the-shelf IP solver. Finally, we carry out a first attempt to learn strong\nbranching decisions for the TDTSP. At the current state, this method does not\nimprove the running times.\n