Transportation Science · 2001 · 112 citations · 20 references
BusinessIndustrial EngineeringOperations ManagementAuction TheoryOptimizationSchedulingAssignment ProblemsCrew SchedulingScheduling TheoryTransportation ModelsTransportation ProblemsVehicle SchedulingScheduling ProblemsSingle-vehicle SchedulingVehicle AssignmentVehicle Operating Costs
Vehicle scheduling is the process of assigning vehicles to a set of predetermined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and computational aspects of the polynomially solvable case in which there is a single depot and vehicles are identical. A quasiassignment formulation is reviewed and an alternative asymmetric assignment formulation is given. The main contributions of the paper are a new two-phase approach which is valid in the case of a special cost structure, an auction algorithm for the quasiassignment problem, a core-oriented approach, and an extensive computational study. New algorithms are compared with the most successful algorithms for the vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with respect to computation time. Such improvement can, for example, be very important when this particular vehicle-scheduling problem appears as a subproblem in more complex vehicle- and crew-scheduling problems.
20
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Time Constrained Routing and Scheduling
Jacques Desrosiers, Marius M. Solomon, François Soumis et al. · PolyPublie (École Polytechnique de Montréal) · 1992 · 712 citations