A Hybrid Genetic and Simulation Annealing Approach for a Multi-period Bid Generation Problem in Carrier Collaboration
| Autor: | Christian Prins, Haoxun Chen, Elham Jelodari Mamaghani |
|---|---|
| Přispěvatelé: | Laboratoire d'Optimisation des Systèmes Industriels (LOSI), Institut Charles Delaunay (ICD), Université de Technologie de Troyes (UTT)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Troyes (UTT)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Linear programming Computer science Carrier Collaboration Computation Bid Generation Time horizon [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Solver Combinatorial auction Simulated annealing Vehicle routing problem Periodic Vehicle Routing Problem Pickup and Delivery Profit Pickup |
| Zdroj: | 8th International Conference on Operations Research and Enterprise Systems 8th International Conference on Operations Research and Enterprise Systems, Feb 2019, Prague, Czech Republic. pp.307-314, ⟨10.5220/0007369203070314⟩ ICORES |
| Popis: | International audience; In this article, a new vehicle routing problem appeared in carrier collaboration via a combinatorial auction (CA) is studied. A carrier with reserved requests wants to determine within a time horizon of multi periods (days) which requests to serve among a set of selective requests open for bid of the auction to maximize its profit. In each period, the carrier has a set of reserved requests that must be served by the carrier itself. Each request is specified by a pair of pickup and delivery locations, a quantity, and two time windows for pickup and delivery respectively. The objective of the carrier is to determine which selective requests may be served in each period in addition of its reserved requests and determine optimal routes to serve the reserved and selective requests to maximize its total profit. For this NP-hard problem, a mixed-integer linear programming model is formulated and a genetic algorithm combined with simulated annealing is proposed. The algorithm is evaluated on instances with 6 to 100 requests. The computational results show this algorithm significantly outperform CPLEX solver, not only in computation time but also in solution quality. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|