The target visitation arc routing problem
| Autor: | Gilbert Laporte, Jessica Rodríguez-Pereira |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Statistics and Probability
Arc routing Mathematical optimization Information Systems and Management Computer science 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research 01 natural sciences Set (abstract data type) 010104 statistics & probability Modelling and Simulation Revenue Discrete Mathematics and Combinatorics Target visitation 0101 mathematics Preference (economics) Integer programming 021103 operations research Linear ordering problem Order (business) Modeling and Simulation Pairwise comparison Routing (electronic design automation) MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Rodríguez-Pereira, J & Laporte, G 2022, ' The target visitation arc routing problem ', TOP, vol. 30, no. 1, pp. 60-76 . https://doi.org/10.1007/s11750-021-00601-5 |
| DOI: | 10.1007/s11750-021-00601-5 |
| Popis: | This paper studies the target visitation arc routing problem on an undirected graph. This problem combines the well-known undirected rural postman problem and the linear ordering problem. In this problem, there is a set of required edges partitioned into targets, which must be traversed and there are pairwise preferences for the order in which some targets are serviced, which generates a revenue if the preference is satisfied. The aim is to find a tour that traverses all required edges at least once, and offers a compromise between the revenue generated by the order in which targets are serviced, and the routing cost of the tour. A linear integer programming formulation including some families of valid inequalities is proposed. Despite the difficulty of the problem, the model can be used to solve to optimality around 62% of the test instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|