Analysis of the Co-routing Problem in Agent-based Carpooling Simulation
Knapen, Luk et al. — 2012
Résumé (FR)
Cet article analyse le problème de co-routage dans la simulation multi-agent du covoiturage. Le covoiturage nécessite une coopération impliquant la co-planification et le co-routage, ce dernier requérant une optimisation combinatoire. Le modèle agent nécessite des algorithmes auxiliaires qui fournissent des solutions de haute qualité aux problèmes d’optimisation embarqués, invoqués des milliers de fois lors de l’évolution de la société d’agents. Les auteurs formalisent le problème de co-routage et analysent sa complexité algorithmique. Des heuristiques efficaces sont proposées pour résoudre le problème à grande échelle. Les résultats montrent que les algorithmes proposés offrent un bon compromis entre qualité de solution et temps de calcul dans le contexte de la simulation agent.
Summary (EN)
This paper analyzes the co-routing problem in agent-based carpooling simulation. Carpooling requires cooperation involving co-scheduling and co-routing, the latter requiring combinatorial optimization. The agent model requires helper algorithms that deliver high-quality solutions to embedded optimization problems, invoked thousands of times during agent society evolution. The authors formalize the co-routing problem and analyze its algorithmic complexity. Efficient heuristics are proposed to solve the problem at scale. Results show that the proposed algorithms offer a good trade-off between solution quality and computation time in the context of agent simulation.
Points clés
| Aspect | Détail |
|---|---|
| Thème | carpooling-abm |
| Venue | Procedia Computer Science |
| Mots-clés | co-routing, combinatorial optimization, carpooling simulation, agent model, route matching |
| DOI | 10.1016/j.procs.2012.06.107 |