Perspectives on integer programming for time-dependent models.

*(English)*Zbl 1418.90160Summary: Integer programs for solving time-dependent models – models in which decisions have to be made about the times at which activities occur and/or resources are utilized – are pervasive in industry, but are notoriously difficult to solve. In the last few years, interest in the role of discretization in approaches to solve these problems has intensified. One novel paradigm, dynamic discretization discovery, has emerged with the potential to greatly enhance the practical tractability of time-dependent models using integer programming technology. We introduce dynamic discretization discovery, illustrate its use on the traveling salesman problem with time windows, highlight its core principles, and point to opportunities for further research. Relations to other approaches for tackling time-dependent models are also discussed.

##### Keywords:

integer programming; time-expanded network; dynamic discretization discovery; traveling salesman problem with time windows
PDF
BibTeX
XML
Cite

\textit{N. L. Boland} and \textit{M. W. P. Savelsbergh}, Top 27, No. 2, 147--173 (2019; Zbl 1418.90160)

Full Text:
DOI

##### References:

[1] | Abeledo, H.; Fukasawa, R.; Pessao, A.; Uchoa, E., The time dependent traveling salesman problem: polyhedra and algorithm, Math Program Comput, 5, 27-55, (2013) · Zbl 1269.90064 |

[2] | Albiach, J.; Sanchis, J.; Soler, D., An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation, Eur J Oper Res, 189, 789-802, (2008) · Zbl 1146.90363 |

[3] | Anderson, E.; Nash, P.; Philpott, A., A class of continuous network flow problems, Math Oper Res, 7, 501-514, (1982) · Zbl 0498.90031 |

[4] | Arigliano A, Ghiani G, Grieco A, Guerriero E, Plana I (2018) Time-dependent asymmetric traveling salesman problem with time windows: properties and an exact algorithm. Discrete Appl Math. https://doi.org/10.1016/j.dam.2018.09.017 In press · Zbl 1420.90056 |

[5] | Ascheuer, N.; Fischetti, M.; Grötschel, M., Solving the asymmetric travelling salesman problem with time windows by branch-and-cut, Math Program, 90, 475-506, (2001) · Zbl 1039.90056 |

[6] | Baker, EK, Technical note—an exact algorithm for the time-constrained traveling salesman problem, Oper Res, 31, 938-945, (1983) · Zbl 0549.90072 |

[7] | Baldacci, R.; Mingozzi, A.; Roberti, R., New state-space relaxations for solving the traveling salesman problem with time windows, INFORMS J Comput, 24, 356-371, (2012) · Zbl 06599275 |

[8] | Baptiste, P.; Sadykov, R., On scheduling a single machine to minimize a piecewise linear objective function: a compact IP formulation, Naval Res Logist, 56, 487-502, (2009) · Zbl 1182.90040 |

[9] | Belvaux, G.; Wolsey, L., bc-prod: a specialized branch-and-cut system for lot-sizing problems, Manag Sci, 46, 724-738, (2000) · Zbl 1231.90384 |

[10] | Belvaux, G.; Wolsey, L., Modelling practical lot-sizing problems as mixed-integer programs, Manag Sci, 47, 993-1007, (2001) · Zbl 1232.90169 |

[11] | Boland, N.; Kalinowski, T.; Kaur, S., Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: bounds and solution strategies, Comput Oper Res, 64, 113-129, (2015) · Zbl 1349.90319 |

[12] | Boland, N.; Clement, R.; Waterer, H., A bucket indexed formulation for nonpreemptive single machine scheduling problems, INFORMS J Comput, 28, 14-30, (2016) · Zbl 1338.90159 |

[13] | Boland, N.; Hewitt, M.; Marshall, L.; Savelsbergh, M., The continuous time service network design problem, Oper Res, 65, 1303-1321, (2017) · Zbl 1380.90069 |

[14] | Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 145-164, (1981) · Zbl 0458.90071 |

[15] | Clautiaux, F.; Hanafi, S.; Macedo, R.; Voge, M-E; Alves, C., Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints, Eur J Oper Res, 258, 467-477, (2017) · Zbl 1394.90477 |

[16] | Dash, S.; Günlük, O.; Lodi, A.; Tramontani, A., A time bucket formulation for the travelling salesman problem with time windows, INFORMS J Comput, 24, 132-147, (2012) · Zbl 06599260 |

[17] | Fischer, F.; Helmberg, C., Dynamic graph generation for the shortest path problem in time-expanded networks, Math Program Ser A, 143, 1-16, (2014) |

[18] | Focacci, F.; Lodi, A.; Milano, M., A hybrid exact algorithm for the TSPTW, INFORMS J Comput, 14, 403-417, (2002) · Zbl 1238.90054 |

[19] | Foschini, L.; Hershberger, J.; Suri, S., On the complexity of time-dependent shortest paths, Algorithmica, 68, 1075-1097, (2014) · Zbl 1317.68069 |

[20] | Gouveia, L.; Ruthmair, M., Load-dependent and precedence-based models for pickup and delivery problems, Comput Oper Res, 63, 56-71, (2015) · Zbl 1349.90087 |

[21] | Gouveia, L.; Leitner, M.; Ruthmair, M., Layered graph approaches for combinatorial optimization problems, Comput Oper Res, 102, 22-38, (2019) · Zbl 1458.90612 |

[22] | He E, Boland N, Nemhauser G, Savelsbergh M (2019) Dynamic discretization discovery algorithms for time-dependent shortest path problems. Optimization Online 2019-7082 |

[23] | Irnich, S., Resource extension functions: properties, inversion, and generalization to segments, OR Spectr, 30, 113-148, (2008) · Zbl 1133.90309 |

[24] | Irnich, S.; Desaulniers, G.; Desaulniers, G. (ed.); Desrosiers, J. (ed.); Solomon, MM (ed.), Shortest path problems with resource constraints, (2005), Boston, MA |

[25] | Irnich, S.; Desaulniers, G.; Desrosiers, J.; Hadjar, A., Path-reduced costs for eliminating arcs in routing and scheduling, INFORMS J Comput, 22, 297-313, (2010) · Zbl 1243.90064 |

[26] | Kara, I.; Derya, T., Formulations for minimizing tour duration of the traveling salesman problem with time windows, Procedia Econ Finance, 26, 1026-1034, (2015) |

[27] | Lagos F, Boland N, Savelsbergh M (2018) The continuous time inventory routing problem. Optimization Online 2018-6439 |

[28] | Langevin, A.; Desrochers, M.; Desrosiers, J.; Gélinas, S.; Soumis, F., A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows, Networks, 23, 631-640, (1993) · Zbl 0792.90084 |

[29] | Mahmoudi, M.; Zhou, X., Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations, Transp Res Part B Methodol, 89, 19-42, (2016) |

[30] | Marshall L, Boland N, Hewitt M, Savelsbergh M (2018) Interval-based dynamic discretization discovery for solving the continuous-time service network design problem. Optimization Online 2018-6883 |

[31] | Montero, A.; Méndez-Dıaz, I.; Miranda-Bront, J., An integer programming approach for the time-dependent traveling salesman problem with time windows, Comput Oper Res, 88, 280-289, (2017) · Zbl 1391.90613 |

[32] | Pesant, G.; Gendreau, M.; Potvin, J.; Rousseau, J., An exact constraint logic programming algorithm for the traveling salesman problem with time windows, Transp Sci, 32, 12-29, (1998) · Zbl 0987.90086 |

[33] | Pessoa, A.; Uchoa, E.; Poggi de Aragao, M.; Rodrigues, R., Exact algorithm over an arc-time indexed formulation for parallel machine scheduling problems, Math Program Comput, 2, 259-290, (2010) · Zbl 1208.90119 |

[34] | Philpott, AB, Continuous-time flows in networks, Math Oper Res, 15, 640-661, (1990) · Zbl 0719.90030 |

[35] | Philpott, A.; Craddock, M., An adaptive discretization algorithm for a class of continuous knapsack problems, Networks, 26, 1-11, (1995) · Zbl 0840.90064 |

[36] | Picard, J-C; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Oper Res, 26, 86-110, (1978) · Zbl 0371.90066 |

[37] | Pugliese, LDP; Guerriero, F., A survey of resource constrained shortest path problems: exact solution approaches, Networks, 62, 183-200, (2013) · Zbl 1338.90432 |

[38] | Riedler M, Ruthmair M, Raidl G (2018) Strategies for iteratively refining layered graph models. Researchgate 328314707 |

[39] | Savelsbergh, M., Local search in routing problems with time windows, Ann Oper Res, 4, 285-305, (1985) |

[40] | Skutella, M.; Cook, W. (ed.); Lovász, L. (ed.); Vygen, J. (ed.), An introduction to network flows over time, 451-482, (2009), Berlin · Zbl 1359.90020 |

[41] | Vu DM, Boland N, Hewitt M, Savelsbergh M (2018) Solving time dependent traveling salesman problems with time windows. Optimization Online 2018-6640. Transp Sci (to appear) |

[42] | Wang, X.; Regan, A., Local truckload pickup and delivery with hard time window constraints, Transp Res B, 36, 97-112, (2002) |

[43] | Wang, X.; Regan, A., On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints, Comput Ind Eng, 56, 161-164, (2009) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.