B GIO DC V O TO TRNG I HC BCH KHOA H NI - NGUYN CH THANH BI TON GIAO THễNG TAXI BUS H NI Chuyờn ngnh : Cụng ngh thụng tin LUN VN THC S K THUT CễNG NGH THễNG TIN NGI HNG DN KHOA HC : TS PHAN THUN H Ni Nm 2014 Bi toỏn giao thụng taxi bus H Ni LI CAM OAN Tụi Nguyn Chớ Thanh - Cam kt lun ny l cụng trỡnh nghiờn cu ca bn thõn tụi di s hng dn ca TS Phan Thun Cỏc kt qu nờu lun l trung thc, khụng phi l chộp ton ca bt k cụng trỡnh no khỏc Bi toỏn giao thụng taxi bus H Ni LI CM N Trc ht, tụi xin gi li cm n trõn trng nht ti TS Phan Thun, b mụn Khoa hc mỏy tớnh, Vin Cụng ngh thụng tin v Truyn thụng, trng i hc Bỏch Khoa H Ni, ngi ó hng dn, tn tỡnh ch bo v h tr tụi sut quỏ trỡnh lm ỏn tt nghip Tụi xin gi li cỏm n ti cỏc thy cụ Vin Cụng ngh thụng tin v Truyn thụng cựng ton th cỏc thy cụ trng i hc Bỏch Khoa H Ni ó cựng giỳp , h tr tụi sut quỏ trỡnh nghiờn cu v thc hin lun ny H Ni, ngy 22 thỏng 03 nm 2014 Hc viờn: Nguyn Chớ Thanh Bi toỏn giao thụng taxi bus H Ni MC LC MC LC DANHMC HèNHV DANH MC CC BNG DANH MC CC T VIT TT CHNG 1: TNG QUAN H THNG GIAO THễNG TAXI BUS H NI 10 1.1 Kho sỏt v ỏnh giỏ thc trng h thng hin ti 10 1.2 Mc tiờu cho h thng mi 14 1.3 í tng cho gii phỏp mi cú cõn nhc tớnh kh thi 15 1.3.1 Phỏc gii phỏp 15 1.3.2 Tớnh kh thi 15 1.3.3 K hoch d ỏn cựng vi d trự tng quỏt 20 CHNG 2: BI TON NH TUYN XE VRP 22 2.1 Gii thiu bi toỏn 22 2.2 Cỏc bin th ca bi toỏn VRP 23 2.3 Cỏc hng tip cn 27 2.4 Bi toỏn giao thụng taxi bus H ni 32 CHNG 3: PHN TCH H THNG 36 3.1 Phõn tớch v chc nng 36 3.1.1 Biu phõn cp chc nng 36 3.1.2 c t cỏc chc nng lỏ 37 3.2 Quy trỡnh nghip v 39 3.2.1 Biu lung d liu mc khung cnh 39 3.2.2 Biu lung d liu mc nh 39 3.2.3 Biu lung d liu mc di nh 40 CHNG 4: THIT K H THNG 46 4.1 Thit k mụ hỡnh tng th 46 4.1.1 Hon chnh cỏc DFD h thng 46 4.1.2 Kin trỳc h thng 50 4.2 Thit k d liu 53 4.2.1 Thit k logic CSDL 53 4.2.2 Thit k CSDL Vt lý 56 4.3 Thit k giao din 59 4.4 Thit k bỏo cỏo 60 CHNG 5: CI T TH NGHIM H THNG 60 5.1 Ci t h thng th nghim 60 5.1.1 Ci t CSDL 60 5.1.2 Ci t chng trỡnh 64 Bi toỏn giao thụng taxi bus H Ni 5.1.2.1 Gii thut phõn nhúm khỏch hng trc ca Fisher v Jakuma 64 5.1.2.2 Gii thut Tabu Search 65 5.2 Mt s hỡnh nh ca h thng 66 CHNG 6: KT LUN 68 6.1 ó lm c 68 6.2 Hn ch 68 6.3 Hng phỏt trin 68 TI LIU THAM KHO 69 Bi toỏn giao thụng taxi bus H Ni DANHMC HèNHV Hỡnh Mụ hỡnh qun lý phng tin giao thụng bng GPS 16 Hỡnh Giao din h thng thc t gpsgiaothong.vn 18 Hỡnh Bỏo cỏo hot ng ca xe trờn h thng thc t 19 Hỡnh Theo dừi l trỡnh xe trờn h thng thc t 19 Hỡnh Tỡm kim thụng tin ca xe h thng thc t 19 Hỡnh Biu phõn cp chc nng 37 Hỡnh Biu lung d liu mc khung cnh 39 Hỡnh Biu lung d liu mc nh 40 Hỡnh Biu lung d liu chc nng qun lý khỏch hng 41 Hỡnh 10 Biu lung d liu chc nng qun lý bn 42 Hỡnh 11 Biu lung d liu chc nng qun lý xe 43 Hỡnh 12 Biu lung d liu chc nng nh tuyn xe 44 Hỡnh 13 Biu lung d liu chc nng bỏo cỏo 45 Hỡnh 14 Biu lung h thng ca chc nng qun lý khỏch hng 46 Hỡnh 15 Biu lung h thng ca chc nng qun lý bn 47 Hỡnh 16 Biu lung h thng ca chc nng qun lý xe 48 Hỡnh 17 Biu lung h thng chc nng ca iu phi xe 49 Hỡnh 18 Biu lung h thng ca chc nng bo bỏo 50 Hỡnh 19 Mụ hỡnh ng dng lp 51 Hỡnh 20 S ERD iu phi taxi - bus 55 Hỡnh 21 Giao din bỏo cỏo ca h thng 59 Hỡnh 22 Mó thut toỏn clustering 65 Hỡnh 23 Giao din h thng th nghim 66 Hỡnh 24 Hin th thụng tin iu xe 67 Bi toỏn giao thụng taxi bus H Ni DANH MC CC BNG Bng Thng kờ s lng Taxi ang hot ng kinh doanh H ni hin 12 Bng D trự thit b ca gii phỏp 20 Bng Liờn kt gia cỏc thc th 54 Bng Bng in bỏo cỏo 60 Bi toỏn giao thụng taxi bus H Ni DANH MC CC T VIT TT T vit tt Chỳ gii VTHKCC Vn ti hnh khỏch cụng cng VRP Bi toỏn nh tuyn xe (Vehicle Routing Problem) DFD Biu lung d liu (Data Flow Diagram) CSDL C s d liu GPS H thng nh v ton cu (Global Positioning System) GPRS Dch v truyn tin qua súng radio (General Packet Radio Service) SMS Dch v thụng bỏo tin ngn (Short Message Services) GIS H thng thụng tin a lý (Geographic Information System) Bi toỏn giao thụng taxi bus H Ni CHNG 1: TNG QUAN H THNG GIAO THễNG TAXI BUS H NI 1.1 Kho sỏt v ỏnh giỏ thc trng h thng hin ti H Ni hin vi tng din tớch 922,8km cựng vi din tớch rt ln c sỏp nhp t tnh H Tõy (c) ú ni thnh l trờn 70km , gm Qun ni thnh c, qun H ụng, Bc T Liờm, Nam T Liờm (mi) cựng th xó Sn Tõy v nhiu huyn ngoi thnh khỏc Dõn s H Ni hin khong trờn 3,5 triu ngi, ngoi thng xuyờn cũn cú mt lng khỏch vóng lai v c dõn ti cỏc tnh xung quanh trung v H Ni lm n sinh sng a dõn s lờn trờn 4,2 triu ngi Vi tc tng trng kinh t bỡnh quõn 9,7% nm H Ni ang l mt trung tõm chớnh tr, kinh t, hoỏ ln xng ỏng Th ụ ca c nc Hn na, lng khỏch Quc t du lch, cụng tỏc, thng mi vo Vit Nam ngy cng tng nhanh v s khỏch n H Ni cng khụng ngng phỏt trin Nhu cu phỏt trin Du lch ngy cng tng ca c nc v xu th hi nhp v hot ng kinh doanh du lch khu vc cng nh trờn th trng th gii Vn chuyn hnh khỏch l mt dch v cu thnh sn phm du lch m hot ng du lch khụng th thiu c Ngoi ra, trờn a bn Thnh ph H Ni cú hn 200 Giy phộp u t, hng trm phũng i din v Chi nhỏnh Ngõn hng nc ngoi T l gia tng hng nm ca s khỏch sn v phũng i din cỏc nm va qua ti Thnh ph H Ni khong 8% nm Ngi nc ngoi lm vic cỏc c s nycú nhu cu s dng phng tin cú sn nc i li rt nhiu, thay vỡ s dng phng tin cỏ nhõn, t trang b cú chi phớ rt cao Tuy nhiờn cú mt ang lm cho khụng nhng ch riờng H Ni m c cỏc thnh ph ca cỏc nc ang phỏt trin cng phi quan tõm: ú l kinh t tng trng vi tc nhanh lm cho c s h tng khụng phỏt trin theo kp Ni thnh H Ni cú hn 400 ng ph vi tng chiu di hn 300km Nhng mng li ng 10 Bi toỏn giao thụng taxi bus H Ni phõn b khụng u, cht lng thp, ng hp ó nh hng rt ln n hot ng giao thụng m c bit l giao thụng cụng cng Qua nghiờn cu xu hng phỏt trin ti hnh khỏch cụng cng (VTHKCC) cỏc thnh ph ca cỏc nc phỏt trin cng nh ang phỏt trin u cú chung mt quan im ú l: i vi mt thnh ph cú s dõn trờn triu ngi nh H Ni hin nay, gii quyt c nhu cu i li thỡ nht thit phi cú h thng VTHKCC ch yu: ú l Tu in ngm v xe Buýt cụng cng Nhng hin H Ni cha cú tu in ngm m nu cú thỡ cng phi tng lai 10-15 nm na Bi vy h thng VTHKCC hin ch yu da vo 1.000 xe buýt cỏc loi v khong 2.650 xe Taxi Xe Buýt H Ni hin ang ngy mt m rng cỏc tuyn, cht lng phc v v c bn ó c nõng cao nhng cũn rt nhiu hn ch, khụng tin li i vi hu ht ngi dõn tham gia s dng phng tin ti cụng cng Cỏc tuyn ng nh, khu dõn c buụn bỏn v ngoi gi phc v ca cỏc tuyn xe buýt nờn khụng trỏnh s bt li tham gia s dng loi phng tin ny Ngoi mng li ng phõn b khụng u, cht lng thp, ng hp S ng ph cú th b trớ xe Buýt chy qua chim 60% nhng trung ch yu vo cỏc tuyn ng chớnh, kh nng phỏt trin mng li xe buýt ph khp H Ni l khụng th thc hin c Trong mt vi nm gn õy, Thnh ph rt chỳ trng u t m rng v nõng cp c s h tng giao thụng, vy kh nng phỏt trin cỏc loi hỡnh ti hnh khỏch cụng cng cú sc chuyờn ch ln khu vc ni thnh l ht sc hn ch Do vy cỏc phng tin ti cụng cng nh MINIBUS, Taxi ang cú xu hng phỏt trin mnh Giao thụng taxi phc v cho cỏc i tng cú nhu cu i li vi yờu cu cao v thi gian v cht lng phc v: nhanh chúng, an ton, tin nghi v chuyn hnh khỏch ti cỏc tuyn ng hp m xe bus khụng th vo c i tng ch yu s 11 Bi toỏn giao thụng taxi bus H Ni geojson text, timestart integer, currentloc text, lat double precision, lon double precision, timestay integer, source integer, target integer, length double precision, bfinished integer ) 4.3 Thit k giao din Giao din ca Web Client cú cỏc chc nng chn nh: Mn hỡnh hin th Xem kt qu nh tuyn xe (minibus dispatch) Tỡm kim Bỏo cỏo Hỡnh 21 Giao din bỏo cỏo ca h thng 59 Bi toỏn giao thụng taxi bus H Ni 4.4 Thit k bỏo cỏo Bỏo cỏo dng bng in: Bng Bng in bỏo cỏo Xe Lỏi Khỏch L Thi gian bt Thi xe hng trỡnh u gian Chi kt thỳc khỏc phớ Trng thỏi CHNG 5: CI T TH NGHIM H THNG 5.1 Ci t h thng th nghim 5.1.1Ci t CSDL 5.1.1.1 Postgresql, Postgis v c trng ca CSDL khụng gian a)Postgresql Vo nm 1986, giỏo s i hc California Berkeley v chuyờn gia cụng ngh v c s d liu Michael Stonebraker ó a l phi xõy dng h thng c s d liu tt hn Mc dự ó cú nhng thnh cụng vi d ỏn c s d liu trc ú, INGRES nghiờn cu ra, Stonebraker ó quyt nh phỏt trin lờn da trờn nn tng ó cú V kt qu ca s phỏt trin ú l Postgres Trong nm tip ú, POSTGRES ó phỏt trin mt cỏch ph bin, c bit l cng ng nghiờn cu Qua mt quỏ trỡnh phỏt trin lõu di, bn PostgreSQL 6.0 c chớnh thc i nú da trờn nn tng ca POSTGRES trc ú v thờm vo cỏc thc thi SQL Ngy nay, PostgreSQL l mt nhng d ỏn ngun m ph bin nht trờn Internet PostgreSQL l h thng qun tr c s d liu quan h i tng da trờn POSTGRES bn 4.2, c phỏt trin ti trng i hc California ti phũng nghiờn 60 Bi toỏn giao thụng taxi bus H Ni cu mỏy tớnh Berkeley Nú l mt chng trỡnh mó ngun m xõy dng trờn mó ngun ban u ca i hc Berkeley Nú h tr mt phn rt ln cho SQL chun v cung cp nhiu tớnh nng hin i nh : Cỏc truy phc Khúa ngoi Trigger Khung nhỡn Tớnh ton ca cỏc giao dch Kim tra truy cp ng thi a phiờn bn Ngoi ra, PostgreSQL cú th c m rng bi nhiu ngi dựng bng nhiu cỏch, vớ d, ngi dựng cú th thờm kiu d liu, hm, toỏn t, hm hp, phng thc ỏnh ch mc v ngụn ng th tc b) PostGIS PostGIS c Refraction Research Inc phỏt trin, nh mt d ỏn nghiờn cu cụng ngh CSDL khụng gian PostGIS h tr i tng a lý cho CSDL i tng quan h PostgreSQL PostGIS kớch hot kh nng khụng gian cho PostgreSQL, cho phộp PostgreSQL s dng nh mt CSDL khụng gian ph tr cho cỏc h thng thụng tin a lý (GIS) c im ca PostGIS : Do PostGIS c s dng nh mt CSDL khụng gian, nờn nú bao gm tt c cỏc c im ca CSDL khụng gian Nú cũn cú nhng c trng nh: Cỏc kiu d hỡnh hc nh Point, Linestring, Polygon, Multipoint, multilinestring, Multipolygons v Geometrycollection Cỏc kiu d liu hỡnh hc ny c lu tr nh nhng i tng hỡnh hc Cỏc toỏn t khụng gian cho phộp xỏc nh cỏc phộp o khụng gian a lý nh tớnh din tớch, tớnh khong cỏch, tớnh di, v tớnh chu vi PostGIS h tr 61 Bi toỏn giao thụng taxi bus H Ni cỏc hm nh: ST_Area(), ST_Length(), ST_Perimeter(), ST_Distance()cỏc hm ny thng thc hin chc nng kiu phộp o Cỏc toỏn t khụng gian cho phộp xỏc nh khụng gian a lý Cỏc thao tỏc nh phộp hp, so sỏnh s khỏc gia cỏc i tng hỡnh hc Cỏc toỏn t c PostGIS h tr lm vic ny cú th l : ST_Difference(): tr v phn khỏc gia i tng hỡnh hc hay hm ST_Buffer() PostGIS cung cp vic ỏnh ch mc khụng gian tc cao s dng GisT hoc R-tree Cụng c ỏnh ch mc khụng gian m PostGIS h tr lm tng tc cho truy khụng gian c bit l trờn bng d liu ln 5.1.1.2 D liu bn OpenStreetMap Mụ hỡnh d liu OpenStreetMap l mt cỏch n gin v mnh m biu din thụng tin a lý Trong cỏc h thng thụng tin a lý truyn thng, d liu bn c biu din ba cỏch khỏc nhau: mt im (point) l mt v trớ n l khụng gian c nh ngha bi cỏc ta , mt ng thng (linestring) l mt ng tuyn tớnh biu din mt ng ph hoc mt ng biờn, v mt hỡnh a giỏc (polygon) l mt khu vc khộp kớn Trong OpenStreetMap, cỏc khỏi nim ny c ct gi di nhng tờn th nodes, ways v relations Cu trỳc d liu OpenStreetMap: 62 maxlat="54.0913900" Bi toỏn giao thụng taxi bus H Ni 63 Bi toỏn giao thụng taxi bus H Ni import vo CSDL postgresql, cú th s dng mt s cụng c osm2pgsql, shp2pgsql, osm2po, Osmosis, 5.1.2 Ci t chng trỡnh Vic ci t h thng giao thụng taxi bus lun s dng mt s thut toỏn Local search, v gii thut to phõn nhúm khỏch hng trc tỡm ng i 5.1.2.1 Gii thut phõn nhúm khỏch hng trc ca Fisher v Jakuma Gi s s lng cỏc phng tin c cho l c nh, ú: 64 Bi toỏn giao thụng taxi bus H Ni Hỡnh 22 Mó thut toỏn clustering 5.1.2.2 Gii thut Tabu Search Mó gi ca gi thut Tabu search: void search(){ initSolution(); updateBest(); it = 1; while(it < maxIt){ if(nic > maxStable){ tbl = tbl + tinc; if(tbl > tbMax){ per{ormRestart(); 10 }else{ 11 updateTabuLists(); 12 } 13 nic = 1; 14 } 65 Bi toỏn giao thụng taxi bus H Ni 15 if(localmove()){ 16 updateBest(); 17 }else{ 18 per{ormRestart(); 19 } 20 it++; 21 } 22.} 5.2 Mt s hỡnh nh ca h thng Mt s hỡnh nh: Hỡnh 23 Giao din h thng th nghim 66 Bi toỏn giao thụng taxi bus H Ni Hỡnh 24 Hin th thụng tin iu xe 67 Bi toỏn giao thụng taxi bus H Ni CHNG 6: KT LUN 6.1 ó lm c V mt lý thuyt: - Phõn tớch, ỏnh giỏ c thc trng ca h thng taxi bus H ni - Hiu c bi toỏn VRP v a dng bi toỏn VRP mi cho h thng taxi bus, xut gii thut gii bi toỏn - xut mụ hỡnh h thng mi tit kim c chi phớ v thun li cho hnh khỏch V mt thc nghim, lun ó thu c mt s kt qu: - Ci t h thng th nghim v thc hin kim tra trờn b d liu th nghim 6.2 Hn ch - B d liu th nghim cũn cha phong phỳ, thiu ỏnh giỏ kt qu 6.3 Hng phỏt trin - Th nghim vi nhiu b d liu hn v ỏnh giỏ - Ci tin gii thut gii bi toỏn giao thụng taxi - bus ti u hn - Nõng cao tớnh thc t ca ti 68 Bi toỏn giao thụng taxi bus H Ni TI LIU THAM KHO [1] G Clarke and J.V Wright (1964), Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, vol 12, pp 568-581 [2] V Nagarajan and R Ravi (2007), Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems,in Proceedings of the the 10th International Workshop on Approximation(APPROX '07), Barcelona, Spain, pp 257270 [3] G Laporte, M Gendreau , J Y Potvin, F Semet, Classical and Modern Heuristics for the Vehicle Routing Problem, International Transaction in Operational Research, vol 7, pp 285-300 [4] G Laporte (2009), Fifty Years of Vehicle Routing, Les Cahiers du GERAD, HEC Montrộal, G200943, 19 [5] J F Cụtộ, J Y Potvin (2008), A tabu search heuristic for the vehicle routing problem with private fleet and common carrier,European Journal of Operational Research, 198(2), pp 464-469 [6] Li, F., Golden, B.L., and Wasil, E.A (2005), Very large-scale vehicle routing: New test problems, algorithms, and results, Computers and Operations Research, vol 32, 1165-1179 [7] Cordeau, J.-F., Laporte, G., and Mercier (2004), A Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows, Journal of the Operational Research Society, vol 55, pp 542546 [8] Prins, C (2004), A simple and eective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research, vol 3, pp 19852002 [9] Reimann, M., Doerner, K., and Hartl, R.F D-Ants (2004), Savings based ants divided and conquer the vehicle routing problem, Computers & Operations Research, vol 31, pp 563-591 [10] A.C.Wade, S Salhi (2002), An investigation into a new class of vehicle routing problem with backhauls, the International Journal of Management Science, vol 30, pp 479 487 [11] Baldacci, R., Battarra, M., Vigo, D., Golden, B., Raghavan, S and Wasil, E (2007), Routing a heterogeneous fleet of vehicles, in B.Golden, S.Ragavan and E.Wasil (editors), The Vehicle Routing Problem: Latest 69 Bi toỏn giao thụng taxi bus H Ni Advances and New Challenges, Springer-Verlag, Heidelberg, Germany, pp 3-29 [12] Wứhlk, S., A decade of capacitated arc routing (2007), in B.Golden, S.Ragavan and E.Wasil (editors), The Vehicle Routing Problem: Latest Advances and New Challenges, Springer-Verlag, Heidelberg, Germany, pp 29-48 [13] C Archetti, M.G Speranza (2008), The split delivery vehicle routing problem: a survey, in B.Golden, S.Ragavan and E.Wasil (editors), The Vehicle Routing Problem: Latest Advances and New Challenges, Springer-Verlag, Heidelberg, Germany, pp 3-29 [14] P Shaw (1998), Using constraint programming and local search methods to solve vehicle routing problems, in Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP98), Pisa, Italy,pp 417431 [15] N Christodesand, S Eilon (1969), An algorithm for the vehicle dispatching problem, Operational Research Quarterly, vol 20, pp 309 318 [16] J.D.C Little, K.G Murty,D.W Sweeney and C Karel(1963), An algorithm for the travelling salesman problem, Operations Research, vol 11, pp 972989 [17] G Laporte, H Mercure and Y Nobert (1986), An exact algorithm for the asymmetrical capacited vehicle routing problem, Networks, vol 16, pp 3346 [18] N Christodes, A Mingozzi and P Toth (1981), Exact algorithms for the vehicle routing problem, based on spanning tree shortest path relaxations, Mathematical Programming, vol 20, pp 255282 [19] D Houck, J.C Picard, M Queyranne and R Vemuganti (1980), The travelling salesman problem as a constrained shortest path problem: Theory and computation experience, Opsearch, vol 17, pp 93109 [20] M.L Fisher(1994), Optimal solution of vehicle routing problems using minimum K-trees, Operations Research, vol 42, pp 626642 [21] S Ropke and D Pisinger (2006) An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,Transportation Science, vol 40, pp 455472 [22] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N, Teller, A.H., Teller, E.(1953), Equation of State Calculation by Fast Computing Machines, Journal of Chemistry and Physical, vol 21, pp 1087-1091 70 Bi toỏn giao thụng taxi bus H Ni [23] Kirkpatrick, S , Gelatt, C.D, Vecchi, M.P (1983) Optimization by Simulated Annealing, Science, vol 220 (4598), pp 671-680 [24] William D Harvey , Matthew L Ginsberg (1995), Limited discrepancy search, in Proceedings of the 14th international joint conference on Artificial intelligence (IJCAI-95), Montreal, Quebec, Canada, pp 607-613 [25] Russell Bent , Pascal Van Hentenryck (2004), A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows, Transportation Science, vol 38 (4), pp 515-530 [26] David Mester , Olli Brọysy (2005), Active guided evolution strategies for large-scale vehicle routing problems with time windows, Computers and Operations Research, vol 32 (6), pp 1593-1614 [27] E Prescott-gagnon, G Desaulniers, L M Rousseau (2009), A branchand-price-based large neighborhood search algorithm for the vehicle routing problem with time windows, Networks, vol 54(4), pp 190-204 [28] David Pisinger , Stefan Ropke (2007), A general heuristic for vehicle routing problems, Computers and Operations Research, vol 34 (8), pp 2403-2435 [29] B.E Gillett and L.R Miller (1974), A heuristic algorithm for the vehicle dispatch problem, Operations Research, vol 22, pp 340349 [30] M Fisher and R Jaikumar (1982), A generalized assignment heuristic for vehicle routing, Networks, vol 11, pp 109124 [31] B.M Baker and J.Sheasby (1999), Extensions to the generalised assignment heuristic for vehicle routing, European Journal of Operational Research, vol.119, pp 147157 [32] C.D Tarantilis (2005), Solving the vehicle routing problem with adaptive memory programming methodology, Computers & Operations Research, vol 32, pp 23092327 [33] M Desrochers, J Lenstra, M Savelsbergh, and F Soumis (1988), Vehicle routing with time windows: optimization and approximation, In Bruce L Golden and Arjang A Assad (editors),Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, pp 65 84 [34] N Bansal , A Blum , S Chawla , A Meyerson (2004), Approximation algorithms for deadline-TSP and vehicle routing with time-windows, in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing(STOC '04), New York, USA 71 Bi toỏn giao thụng taxi bus H Ni [35] S Ropke (2005), Heuristic and exact algorithms for vehicle routing problems, Ph.D Thesis, Computer science department at the University of Copenhagen (DIKU) [36] B.E Gillet and L.R Miller (1974), A heuristic algorithm for the vehicledispatch problem Operations Research, vol 22, pp 340349 [37] G Laporte and F Semet (2002), Classical heuristics for the capacitated VRP, In P Toth and D Vigo (Editors), The Vehicle Routing Problem, SIAM, Philadelphia, pp 109-149 [38] Khoa Tran, Nguyen Dang, Tien Dinh (2011), On a Real-World Variant of theVehicle Routing Problem, accepted in poster session of the 3rd Asian conference on Intelligent Information and Database Systems (ACIIDS 2011) [39] Ortega, P., Oliva, C., Ferland, J., Cepeda M.(2009), Multiple ant colony system for a VRP with time windowsand scheduled loading IngeniareRevista chilena de ingeniera, vol 17, pp 393403 [40] F Glover (1989), Tabu Search - part I, ORSA Journal on Computing, vol.1 (3), pp 190-206 [41] M Gendreau, J Y Potvin, O Braysy, G Hasle, A Lứkketangen (2007), Metaheuristics for the Vehicle Routing Problem and Its Extensions: A CategorizedBibliography, in B.Golden, S.Ragavan and E.Wasil (editors), The Vehicle Routing Problem: Latest Advances and New Challenges, Springer-Verlag, Heidelberg, Germany, pp 143-169 [42] I Zeng, H.L Ong and K.M Ong (2005) An assignment-based local search method for solving vehicle routing problems, Asia-Pacic Journal of Operational Research, vol 22, pp 85104 [43] F Li, B Golden and E Wasil (2007), A record-to-record travel algorithm for solving the heterogeneous eet vehicle routing problem, Computers & Operations Research, vol 34, pp 2734-2742 [44] L.M Rousseau, M Gendreau and G Pesant (2002) Using constraintbased operators to solve the vehicle routing problem with time windows, Journal of Heuristics, vol 8, pp 43- 58 [45] J Kytojoki, T Nuortio, O Braysy and M Gendreau (2007), An ecient variable neighborhood search heuristic for very large scale vehicle routing problems, Computers & Operations Research, vol 34, pp 2743 2757 72 Bi toỏn giao thụng taxi bus H Ni [46] C.M.R.R Lima, M.C Goldbarg and E.F.G Goldbarg (2005), A Memetic Algorithm for the Heterogeneous Fleet Vehicle Routing Problem, Electronic Notes in Discrete Mathematics Vol 18, pp 171-176 [47] A Chen, G Yang, Z Wu (2006), Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem, Journal of Zhejiang University - Science, vol 7(4), pp 607-614 [48] R E Steuer (1986), Multiple criteria optimization: theory, computation and application, Krieger Publishing Company, USA, 546 73 ... Optimization [47] 2.4 Bài toán giao thông taxi – bus Hà nội Bài toán giao thông taxi - bus biến thể thực tế (kết hợp nhiều biến thể) toán VRP Ngoài ràng buộc thƣờng thấy toán VRP lý thuyết, toán có số ràng... mặt hàng (commodit type) mà xe chở, … - Kho hàng (depot): nơi chứa hàng hóa, xe lấy hàng kho để giao hàng cho khách hàng, sau giao xong, xe quay trở lại kho hàng 22 Bài toán giao thông taxi – bus. .. nhận hàng, nhƣng có chút khác biệt: xe không đến gặp khách hàng để 24 Bài toán giao thông taxi – bus Hà Nội lấy hàng giao cho khách hàng khác mà ràng buộc thứ tự gặp khách hàng là: xe phải giao hàng