Swap-Insert Algorithm for Driver Scheduling Problem

Sang-Un, Lee

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2014, 19(11), pp.175-181
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Sang-Un, Lee ¹

¹강릉원주대학교

ABSTRACT

This paper suggests O(ｍ) polynomial time heuristic algorithm to obtain the solution for the driverscheduling problem, DSP, that has been classified as NP-complete problem. The proposed algorithm getsthe initial assignment of ｎ minimum number of drivers from given ｍ schedules. Nextly, this algorithmgets the minimum total time (TC) using 5 rules of swap and insert for decrease of over times (OT) and idletimes (IT). Although this algorithm is a heuristic polynomial time algorithm with O(ｍ)time complexityrules to be find a optimal (or approximate) solution, this algorithm is equal to metaheuristic methods forthe 5 experimental data. To conclude, this paper shows the DSP is not NP-complete problem butPolynomial time (P)-problem with polynomial time rules.
KEYWORDS

Driver scheduling problem, Parallelogram, Swap, Insert, Idle time
REFERENCES (15)

[journal] A. Wren / 2003 / A Flexible Systemfor Scheduling Drivers / Journal of Scheduling 6(5) : 437~455

[journal] H. R. Lourenço / 2001 / Multiobjective Metaheuristics for the Bus-Driver Scheduling Problem / Transportation Science 35(3) : 331~343

[confproc] S. Groot / 2008 / Vehicle and Crew Scheduling Solving Large Real-World Instances with an Integrated Approach / 9th International Conference onComputer-Aided Scheduling of Public Transport, San Diego, California, Lecture Notes in Economics and Mathematical Systems 600 : 43~56

[confproc] G. R. Mauri / 2004 / Driver Scheduling Generation Using a Population Training Algorithm / Brazilian Symposiumin Neural Networks : 1~6

[journal] G. R. Mauri / 2007 / A New Hybrid Heuristic forDriver Scheduling / International Journal of Hybrid Intelligent Systems 4(1) : 39~47

[journal] H. R. Lourenço / 1998 / Metaheuristics for theBus-Driver SchedulingProblem / Department of Economics andManagement, Universitat Pompeu Fabra 35 : 1~26

[confproc] Y. Shen / 2001 / Tabu Search for Driver Scheduling / Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems / Springer-Velag 505 : 121~135

[confproc] T. G. Dias / 2001 / AGenetic Algorithmfor the Bus Driver Scheduling Problem / 4th InternationalConference ofMetaheuristics : 35~40

[journal] R. Bai / 2013 / A Novel Approach to Independent Taxi Scheduling Problem Based on Stable Matching / Journal of Operational Research Society : 1~10

[journal] R. Portugal / 2009 / Driver Scheduling ProblemModeling / Public Transportation 1(2) : 103~120

[confproc] B. Laurent / 2005 / AHeuristic Solution for a Driver-Vehicle Scheduling Problem / Proceedings of Operations Research 2005 : 703~708

[journal] R. Leone / 2011 / A Bus Driver Scheduling Problem : ANewMathematicalModel and GRASP Approximate Solution / Journal of Heuristics 17(4) : 441~466

[confproc] L. T. Shung / 2009 / An Evolutionary Algorithm Approach to a Bus Driver Scheduling Problemwith Break-Time Consideration / Proceedings of the 5th Asian Mathematical Conference, Malaysia : 652~658

[book] R. M. Karp / 1972 / Complexity of Computer Computations / Plenum Press : 85~103

[web] L. A. N. Lorena / 2014 / Problem Instances: Driver Scheduling / http://www.lac.inpe.br/~lorena/nstancias.html
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools