On some matching problems arising in vehicle scheduling models

1987/01/01 by A. A. Bertossi, Alan A. Bertossi, P. Carraresi +3 · 5 citations
Engineering · #Smart Parking Systems Research #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods

paper · doi:10.1002/net.3230170303

crossref issued 1987/01/01 · crossref published 1987/01/01 · crossref published-print 1987/01/01 · openalex publication_date 1987/01/01 · crossref published-online 2006/10/11 · crossref created 2007/05/11 · crossref deposited 2023/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31 · crossref indexed 2026/07/31

Abstract

Abstract Two bipartite matching problems arising in Vehicle Scheduling are considered: the capacitated matching and the multicommodity matching. For the former, given a reasonable cost structure, we can exhibit a polynomial time algorithm, while the general case is conjectured to be NP‐hard. The latter problem is shown to be NP‐hard. A heuristic algorithm based on Lagrangean relaxation for the capacitated version of the multicommodity matching is also presented together with experimental results.

Citations

• Complexity of vehicle routing and scheduling problems

Cited by

• Integer-Clustering Optimization of Hydrogen and Battery EV Fleets Considering DERs
• Transit Bus Scheduling with Limited Energy
• Charge Schedule Optimization and Infrastructure Planning for Solar-Integrated Electric Bus Transit Systems
• Temporal Routing in Static Networks: The Schedule Completion Problem
• An exact approach for the multi-depot electric vehicle scheduling problem