Abstract Vehicle routing problem är en klassisk kombinatorial optimering problem. Detta arbete handlar om en variant av fordonets routing problem med dynamiskt ändra order och tid fönster. I verkliga tillämpningar ändras ofta kraven under driftstiden. Nya beställningar sker och andra ställs in. I detta fall måste nya scheman genereras på flygningen. Online optimering algoritmer för dynamiska fordon routing ta itu med detta problem, men hittills de inte anser tid fönster. För att matcha scenarierna i verkliga problem krävs dessutom anpassningar av riktmärken. I detta dokument bygger ett praktiskt problem på förfarandet för daglig routing av ett leveransföretag. Nya order från kunder introduceras dynamiskt under arbetsdagen och måste integreras i schemat. En multipel myrkolonialgoritm i kombination med kraftfulla lokala sökprocedurer föreslås för att lösa den dynamiska fordon routing problem med tidsfönster. Prestandan testas på ett nytt riktmärke baserat på simuleringar av en arbetsdag. Problemen tas från Salomos riktmärken, men en viss procent av ordern avslöjas endast för algoritmen under driftstiden. Olika versioner av MACS-algoritmen testas och en högpresterande variant identifieras. Slutligen testas algoritmen på plats: I en fältstudie schemalägger algoritmen en bilflotta för ett övervakningsbolag. Vi jämför algoritmens prestanda med det förfarande som används av företaget och vi sammanfattar insikter som vunnits från genomförandet av den verkliga studien. Resultaten visar att multipelmyrakolonialgoritmen kan få en mycket bättre lösning på det akademiska referensproblemet och även kan integreras i en verklig miljö.
Denna studie fortsatte i REF, där MACS-DVRPTW tillämpades för att schemalägga rutterna för en bilflotta för ett övervakningsbolag.
Dynamic vehicle routing with time windows in theory and practice