{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:24:32Z","timestamp":1754151872198,"version":"3.41.2"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SOCS"],"abstract":"<jats:p>This paper investigates a Traveling Salesman Problem with Time Windows and Vacant Penalties (TSP-TW-VP), which plans a path to service a set of machines at different locations within their respective time windows while minimizing two objective functions: the finish time and penalty for machine vacancy. There is often no single solution that optimizes both objectives simultaneously, and the problem thus seeks the Pareto-optimal solutions. TSP-TW-VP generalizes TSP-TW and is therefore NP-hard. To solve the problem, this paper develops an algorithm called Search with Look-Ahead Pruning (S-LAP) that is guaranteed to find all Pareto-optimal solutions for TSP-TW-VP. S-LAP gains computational efficiency by introducing a novel look-ahead pruning rule, and a fast dominance checking method based on both the objective functions and path history. Experimental results show that the proposed look-ahead pruning and fast dominance can speed up the search for 2-8 times over 4 different datasets.<\/jats:p>","DOI":"10.1609\/socs.v18i1.35989","type":"journal-article","created":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T06:06:59Z","timestamp":1753078019000},"page":"171-179","source":"Crossref","is-referenced-by-count":0,"title":["Bi-Objective Search for the Traveling Salesman Problem with Time Windows and Vacant Penalties"],"prefix":"10.1609","volume":"18","author":[{"given":"Shizhe","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yancheng","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongqiang","family":"Ren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9382","published-online":{"date-parts":[[2025,7,19]]},"container-title":["Proceedings of the International Symposium on Combinatorial Search"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/35989\/38144","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/35989\/38144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T06:07:00Z","timestamp":1753078020000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/view\/35989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,19]]},"references-count":0,"URL":"https:\/\/doi.org\/10.1609\/socs.v18i1.35989","relation":{},"ISSN":["2832-9163","2832-9171"],"issn-type":[{"type":"electronic","value":"2832-9163"},{"type":"print","value":"2832-9171"}],"subject":[],"published":{"date-parts":[[2025,7,19]]}}}