Complexity of Scheduling for DARP with Soft Ride Times
| Autor: | Clément Dallard, Janka Chlebíková, Niklas Paulsen |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
021103 operations research Job shop scheduling Dial a ride Computer science Existential quantification 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Scheduling (computing) 010201 computation theory & mathematics Time windows Bounded function Vehicle routing problem Time complexity |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030174019 CIAC |
| Popis: | The Dial-a-Ride problem may contain various constraints for pickup-delivery requests, such as time windows and ride time constraints. For a tour, given as a sequence of pickup and delivery stops, there exist polynomial time algorithms to find a schedule respecting these constraints, provided that there exists one. However, if no feasible schedule exists, the natural question is to find a schedule minimising constraint violations. We model a generic fixed-sequence scheduling problem, allowing lateness and ride time violations with linear penalty functions and prove its APX-hardness. We also present an approach leading to a polynomial time algorithm if only the time window constraints can be violated (by late visits). Then, we show that the problem can be solved in polynomial time if all the ride time constraints are bounded by a constant. Lastly, we give a polynomial time algorithm for the instances where all the pickups precede all the deliveries in the sequence of stops. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|