Abstrakt. Vi tillhandahåller approximationsalgoritmer för vissa kapacierade fordon routing och leveransproblem. Dessa problem kan alla ses som exempel på följande k-Leverans TSP: givet n-källpunkter och n-sänkpunkter i ett metriska utrymme, med exakt ett objekt vid varje källa, nda en minsta längdtur med ett fordon med nitkapacitet k för att plocka upp och leverera exakt ett objekt till varje diskbänk. Den enda kända approximationsalgoritmen för denna problemfamilj är 2,5-approximationsalgoritmen för Anily och Hassin 2] för specialfallet k = 1. För detta fall använder vi matris skärningspunkt för att få en 2- approximation algoritm. Baserat på denna algoritm och några ytterligare lägre bundet argument, vi utforma en 9,5- approximation för k-Delivery TSP med godtycklig nite k. Vi presenterar också en 2- approximation algoritm för fallet k = 1. Vi initierar sedan studien av dynamiska varianter av k-Delivery TSP som modellerar problem i industriell robotik och andra tillämpningar. Speci caley, vi anser att situationen där en robot arm (med nite eller nite kapacitet) måste samla n punkt-objekt som rör sig i Euclidean planet, och leverera dem till ursprunget. Punktobjekten rör sig i planet med kända, identiska hastigheter { de kan till exempel vara på ett rörligt transportband. Vi härleder flera användbara strukturella egenskaper som leder till konstant-faktor approximationer för problem av denna typ som är relevanta för robotik applikationen. Längs vägen visar vi att Maximum Latency TSP är implicit i de dynamiska problemen, och att den naturliga \furthest granne" heuristic producerar en bra approximation för flera begrepp latency.
Författare i REF studerar en kinetisk variant av den k-leverans TSP där alla mål rör sig med samma hastighet och en robotarm rör sig med en ändlig kapacitet måste fånga upp dem.
Approximating Capacitated Routing And Delivery Problems
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}