Microsoft Word - 2-Format-Yaghini

Size: px

Start display at page:

Download "Microsoft Word - 2-Format-Yaghini"

锐祀濮
4 years ago
Views:

ISSN: 20084870 http://ijiepm.iust.ac.ir/ :.

1 ISSN: :. p n pmedian. (CCP).[] (CCCP) CCP. [] [] []. []. (). 3. Capacitated clustering problem(ccp) 4. Capacitated centered clustering problem(cccp). p n. ) (). ( // : // : yaghini@iust.ac.ir 2. Locationallocation avadlessan@rail.iust.ac.ir

2 ... []..[] CCP.[] CCP.[ ]. [] CCP CPMP. [] CCP CPMP... pmedian CPMP.. ) (. ( ) p CPMP. ( ) () 12. Ahmadi 13. Greedy randomized adaptive search procedure (GRASP) 14. Franca 15. Scheuerer 16. Wendolsky 17. Diaz 18 Fernandez.. pmedian.[] pmedian.[]. (CPMP) pmedian.. [] [].[]. [] /.[].[] CCP (SPP).[] pmedian NP [] hard [].. [] [] 1. Hakimi 2. Klastorin 3. Capacitated pmedian problem(cpmp) 4. Mulvey 5. Beck 6. Pirkul 7. Lorena 8. Senne 9. Baldacci 10. Set partitioning problem (SPP) 11. Boccia

3 ... [ ] ) y {1,..., } 1 n = p y = 1. y = 0 i ( P Q q i. pmedian () :. ( V P) () (). ( ) P ( V P) ().. p () () CCP. [] (SA).. 1. Single solutionbased metaheuristic 2. Populationbased metaheuristic 3. Simulated annealing. CPMP n p np ( ). ( ). NPhard CPMP.[] : CPMP V = {1,2,..., n} p. P = {1, 2,..., p}, ( P V ) p VP V. P ( ). (CCP) v( P) Min di xi i V V : = () St : x = 1 i V V i () x y i, V () i yi = p () V qi xi Q y V (5) i N { } x, y 0,1 i V, V (6) i V = {1,2,..., n} i ( / ) [ d i ] i ( V P) x = 1 [ ] x i n n. x = 0 ( P) i

4 ... CCP. " ".. ( ) ()... (). []..[ ]. CCP.. p.... ().. p ( V P). 1. Haland 2. Chromosome representation. SA. ().. ( E ) E. ().. ( ).. p..... Sim ulated annealing algorithm (S A) 1: s : = G enerateinitailsolution (); 2 : T : = Tm ax ; 3 : T : = T ; 0 m in /*Strating temperature*/ /*Final temperature */ 4 : α : = a ; 5 : Itr : = R ; /*C ooling rate*/ /*Iterations*/ 6 : r : = 0; /*Reset iterations*/ 7 : w hile T > T do ( 0 ) ( r Itr ) 8 : w hile do 9 : r : = r + 1; 10 : s : = G enerateatrandom s N ( s) 11: E = f ( s ) f ( s); 12 : if E 0 13 : s : = s ; 14: else 15: let x [ 0,1]; 16: if E T ( x < e ) 17: s : = s ; 18 : end w hile 19: T : = T α ; 20 : r : = 0; 21: end w hile. K

5 .... ) (. ( ) ) ( V P) (. Genetic algorithm (GA). () 1: t : = 0; 2: pop ( t) : = GenerateInitailPopulation (); /* Initial population */ 3: Evaluate ( pop ( t)); 4: whileterminationcriterion ( pop ( t)) not met do 5: pop ( t): = Select ( pop ( t)); 6: pop ( t) : = Reproduct ( pop ( t)); 7 : pop ( t) : = Improve ( pop ( t)) 8: pop ( t + 1) : = Replace ( pop ( t), pop ( t)); 9: t : = t + 1; 10: end while... ( ) ( ) ( ) Crossover 5. Recombination 6. Mutation 1. Fitness function 2. Parent selection 3. Roulette wheel

6 .... MIP,,,,,,,,,, p n. ( ) A B C Minitab15 α =/ :... ( )..... [] (A)..[] (B) (C).[].[]. Java Pentium IV, CPU DualCore E5200 2GB RAM GHz,.[] /.. %.. 2. MannWhitney 1. ORlibrary

7 .... (,) α. / pvalue pvalue.. ( ). /.[].. SA.... B.. ). (.. () / / / / / / / / / / () / / / / / / / % / % / % / % / % / % / % / % / % / % GA () / / / / / / / / / / / % / % / % / % / % / % / % / % / % / SA. / % / % / % / % / % / % GA / % / % / % / % / % / % () / / / / / / SA. B # # B.. 1. Lagrangean/surrogate relaxation heuristic

8 ..... [ ] VNSLB GA SA / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / % / / % / % / % / % / % / % / % / % / % / % / % # A B C. (%) GA / % / % / % / % / % () SA. ( ) #. p n. pmedian.... B...[] CPLEX..

9 ... [13] Boccia, M., Sforza, A., Sterle, C., Vasilyev, I. A Cut and Branch Approach for the Capacitated pmedian Problem Based on Fenchel Cutting Planes. J Math Model Algor, 7, 1, 2008, pp [14] Garey, M.R., Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, San Francisco, [15] Osman, I.H., Christofides, N., Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search, International Transactions in Operational Research, 1, 3, 1994, pp [16] Chaves, A.A., Lorena L.A.N., Clustering search heuristic for the capacitated pmedian problem. Computers & Operations Research, 37, 2010, pp [17] Chaves, A.A., Lorena, L.A.N., Clustering search heuristic for the capacitated pmedian problem. Springer Advances in Software Computing Series, 44,136 43, [18] Fleszar, K., Hindi, K.S., An Effective VNS for the Capacitated pmedian Problem, European Journal of Operation Research 191, 2008, pp [19] Ahmadi, S., Metaheuristics for the Capacitated Clustering Problem, Dissertation at the University of Kent at Canterbury, [20] Francia, P.M., Sosa, N.M., Pureza, V., An Adaptive Tabu Search Algorithm for the Capacitated Clustering Problem, International Transactions in Operational Research, 6, 6, 1999, pp [21] Scheuerer, S., Wendolsky, R., A Scatter Search Heuristic for the Capacitated Clustering Problem. European Journal of Operational Research, 169, 2006, pp [22] Reese, J., Solution Methods for the pmedian Problem: An Annotated Bibliography, Networks, 48, 3, 2006, pp [23] Mladenovic, N.J., Brimberg, P., Hansen, J.A., Moreno Perez, The pmedian Problem: A Survey of Metaheuristic Approaches, European Journal of Operational Research, 179, 2007, pp [24] Diaz, J.A., Fernandez, E., Hybrid Scatter Search and Path Relinking for the Capacitated pmedian Problem. European Journal of Operational Research, 169, 2, 2006, pp [25] Kirkpatrick, S., Gelatt, C. D., M. Vecchi, P. Optimization by Simulated Annealing, Science 220, , [26] Holland J.H, Adaptation in Natural and Artificial System, Ann Arbor, Michigan: The University of Michigan Press [27] Blum, C., Aguilera, M.J.B., Roli, A., Sampels, M., Hybrid Metaheuristics: An Emerging Approach to Optimization. SpringerVerlag Berlin Heidelberg, [1] Negreiros, M.J.N., Palhano, A.W.C., The Capacitated Centered Clustering Problem, Computers and Operations Research, 33(6): , [2] Fisher, M., Jaikumar, R., A Generalized Assignment Heuristic For The Vehicle Routing Problem, Networks, 11, 2, 1981, pp [3] Koskosidis, Y.A., Powell, W.B., Clustering Algorithms For Consolidation Of Customer Orders Into Vehicle Shipments, Transportation Research B 26, 5, 1992, pp [4] Bozkaya, B., Erkut, E., Laporte, G., A Tabu Search Heuristic and Adaptive Memory Procedure for Political Districting, European Journal of Operational Research, 144, 1, 2003, pp [5] Mulvey, J.M., Beck, M.P., Solving Capacitated Clustering Problems, European Journal of Operational Research, 18, 3, 2003, pp [6] Hakimi, S.L., Optimum Locations of Switching Centers and the Absolute Centers and Medians of A Graph, Operations Research, 12, 1964, pp [7] Klastorin, T., The PMedian Problem for Cluster Analysis: A Comparative Test Using the Mixture Model Approach, Management Science, 31, 84 95, [8] Cornueols, G., Fisher, M.L., Nemhauser, G.L., Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms, Management Science, 23, 1977, pp [9] Maniezzo, V., Mingozzi, A., Baldacci, R., A Bionomic Approach to the Capacitated PMedian Problem, Journal of Heuristics, 4, 3, 1998, pp [10] Pirkul, H., Efficient Algorithms for the Capacitated Concentrator Location Problem, Computers & Operations Research, 14, 3, 1987, pp [11] Lorena, L.A.N., Senne, E.L.F., Local Search Heuristics for Capacitated PMedian Problems, Networks and Spatial Economics, 3, 4, 1987, pp [12] Baldacci, R., Hadiconstantinou, E., Maniezzo, V., Mingozzi, A., A New Method for Solving Capacitated Location Problems Based on a Set Partitioning Approach, Computers and Operations Research, 29, 2002, pp

10 ... [28] Weise, T., Global Optimization Algorithms Theory and Application, University of Kassel, Distributed Systems Group, Thomas Weise, [29] Lorena, L., Senne, E. A Column Generation Approach to Capacitated pmedian Problems, Computers and Operations Research, 31, 6, 2004, pp [30] Beasley, J.E., ORLibrary: Distributing Test Problems by Electronic Mail, Journal of the Operational Research Society, 41, 1990, pp [31] Talbi, El.Gh, Metaheuristics: from design to implementation. John Wiley & Sons, Inc., Hoboken, New Jersey, 2009.

892416H009031

892416H009031 The Study of Mass Rapid Transit Drivers Scheduling Problems A Case Study of Taipei MRT Company Abstract This paper proposes an algorithm to improve the efficiency for solving the drivers scheduling problem