การศ กษาร ปแบบการจ ดเส นทางเพ อท าการวางแผนการการเด นทางของพน กงานขาย Routes with Local Search for Planning Salesman Travelling - PDF

Description
การศ กษาร ปแบบการจ ดเส นทางเพ อท าการวางแผนการการเด นทางของพน กงานขาย Routes with Local Search for Planning Salesman Travelling พ ชรล กษณ ร กธรรมจ รส ข สาขาว ชาการจ ดการเทคโนโลย ว ศวกรรมภาคว ชาเทคโนโลย

Please download to get full document.

View again

of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Word Search

Publish on:

Views: 13 | Pages: 8

Extension: PDF | Download: 0

Share
Transcript
การศ กษาร ปแบบการจ ดเส นทางเพ อท าการวางแผนการการเด นทางของพน กงานขาย Routes with Local Search for Planning Salesman Travelling พ ชรล กษณ ร กธรรมจ รส ข สาขาว ชาการจ ดการเทคโนโลย ว ศวกรรมภาคว ชาเทคโนโลย ว ศวกรรมอ ตสาหการ ว ทยาล ยเทคโนโลย อ ตสาหกรรม มหาว ทยาล ยเทคโนโลย พระจอมเกล าพระนครเหน อ บทค ดย อ งานว จ ยน ม ว ตถ ประสงค เพ อศ กษาเส นทางการเด นทางของพน กงานขาย โดยใช ป ญหาการเด นทางของพน กงานขาย (Travelling Salesman Problem) และว ธ การค นหาแนวล ก(Depth First Search)โดยท าการเปร ยบเท ยบก บว ธ การเด นทางแบบเด ม ท า ให สามารถค นหาเส นทางในการเด นทางไปพบล กค าได ระยะทางรวมท ได น อยท ส ด ท าให เวลาการเด นทางไปพบล กค าท นต อเวลา น ดหมาย ไม เก ดการเหน อยล าจากการเด นทาง เช อเพล งท ใช ไปในการเด นทางให ได ประโยชน จากการเด นทางเหมาะสมต อเส นทาง การเด นทาง ซ งการเด นทางในแบบเด มได ม การวางแผนโดยผ ท ช านาญกว าในการเด นทางโดยอาศ ยประสบการณ เด นทางใน แบบเด มน ามาวางแผนการเด นทาง ผ ท าการว จ ยจ งม การพ ฒนาให ม การวางแผนล วงหน าก อนการเด นทางจร งใน 1 ส ปดาห จากผลการท าการศ กษาโครงการพ เศษพบว าเส นทางเด นรถท ได ประมวลผลโดยได ผลล พธ ว าเส นทางการเด นทางแบบเด ม กรณ ศ กษาภาคกลางส าหร บส ปดาห ท 1 พบว าระยะทางท ลดลง (ก โลเมตร) ส ปดาห ท 2 ระยะทางท ลดลง 64.8(ก โลเมตร) ส ปดาห ท 3 ระยะทางท ลดลง (ก โลเมตร) ส ปดาห ท 4 ระยะทางท ลดลง (ก โลเมตร)ตามล าด บ และเส นทางการเด นทาง เขตปร มณฑล ส าหร บส ปดาห ท 1 พบว าระยะทางท ลดลง (ก โลเมตร) ส าหร บส ปดาห ท 2 พบว าระยะทางท ลดลง 294 (ก โลเมตร) ส าหร บส ปดาห ท 3 พบว าระยะทางท ลดลง (ก โลเมตร) ส าหร บส ปดาห ท 4 พบว าระยะทางท ลดลง (ก โลเมตร) ด งน นการน าเอาทฤษฎ ป ญหาการเด นทางของพน กงานขายมาใช ก ท าให ภาระค าใช จ ายด านการเด นทางลดลงและ ระยะทางในการเด นทางท ลดลง ค าส าค ญ: ป ญหาการเด นทางของพน กงานขาย,ว ธ การค นหาแนวล ก Abstract This research is present to study the routing problem for Travelling Salesman Problem and Depth First Search for compare the old routing. Then give the New routing creates optimal routing for salesman to navigate the shortest route towards customers so that the salesman would be timely for any appointment to meet with customers. Moreover, fuel used for travelling would be positively impacted by the appropriate travel routing, while the salesman would not be fatigue of traveling to meet customers. This research that plan before travel in 1 week. The results of special project about the routes that have been processed out that, the traditional routes in a Case Study of Central Region in week 1 distance are reduce in km,64.8km,147.2km, km, respectively. Whereas, routes in Metropolitan areas in week 1, distance are reduce in km, 294 km,111.28km, km As a result, the deployed Theory of Salesman Traveling Problem makes travel cost to down as well as minimizes the distance to be traveled. Keyword : Travelling Salesman Problem, Depth First Search 6 พฤศจ กายน 1. บทน า ในป จจ บ นม ล วนม การแข งข นก นทางด านอ ตสาหกรรมจ งม ความจ าเป นต องม การวางแผนการเด นทางเพ อลดค าใช จ ายท ไม จ าเป นโดยอาจจะมองถ งป จจ ยต างๆร วมด วยท งในด านการค า การเด นทาง การขนส ง พบว าการต ดต อส อสารท ม ความ หลากหลายท าให ธ รก จต างๆเก ดการขยายต วขององค กรอย าง รวดเร วส งผลถ งด านการขนส ง เหล าน นเปร ยบเสม อนเป นเส น เล อดท น าป จจ ยการผล ตและผลผล ตไปย งท ต างๆท ม ความ ต องการส งผลให เก ดความซ บซ อนของการจ ดเส นทางการ ขนส ง รวมถ งต นท นการขนส งส นค าท ม การปร บต วส งข นท า ให ส งเหล าน เป นส งท องค กรไม สามารถหล กเล ยงได จ งท าให ต องม แบบแผนการวางแผนการเด นทางในการขนส งและการ เด นทางของพน กงาน ด งน นการขนส งท ม ประส ทธ ภาพและม ต นท นต าจ งเป นองค ประกอบหน งท สน บสน นการพ ฒนา เศรษฐก จ จะท าให สามารถลดระทางในการขนส งท าให ต นท น ในการขนส งส นค าลดลง โดยว ตถ ประสงค การว จ ย (1) เพ อศ กษาเส นทางการเด นทาง ของพน กงานขายโดยได ระยะทางการเด นทางรวมน อยท ส ด (2)เม อเท ยบก บระยะเวลาการเด นทางแบบเด ม ได เส นทางการ เด นทางแบบใหม ท าให ม การจ ดล าด บเส นทางการเด นทางได ระยะทางท ลดลง ซ งในป จจ บ นม ผ ค ดว ธ แก ป ญหาน อย หลายแบบ[7]โฉม ได ศ กษาการศ กษาป ญหาการจดมาตรว ดน าโดยว ธ การเด นทาง ของเซลล แมนเพ อหาเส นทางในการเด นรถท ส นท ส ดใช ว ธ การ แก ป ญหาโดยว ธ การเด นทางของเซลล แมน(Traveling Salesman Problem) โดยแบ งว ธ การหาค าตอบเป น 2 ว ธ ค อว ธ ท หน งหาค าตอบท ได ผลล พธ ท ด ท ส ดโดยว ธ การแตกก งและ จ าก ดขอบเขต (Branch And Bound Method) ว ธ ท สองหา ค าตอบท ใกล เค ยงค าค าตอบท ส ดโดยว ธ เน ยเรสเนจ-บอฮ วล สต ก (Nearest Neighbor Heuristic) จ งเห นได ว าว ธ การแตกก ง และจ าก ดขอบเขตสามารถช วยให ประหย ดระยะทางการเด นรถ ประหย ดเวลาและม ผลรวมไปถ งการประหย ดค าใช จ าย [8]ศศ ธรได เสนอ แนวค ดในการออกนอกเส นทาง 5 แนวค ด โดยใช โปรแกรม STROM ในการแก ป ญหาปร มาณเช อเพล งท เหล อในถ งไม ต ดลบตลอดเส นทางและ เส นทางท รถสามารถว ง ได ไกลท ส ด 600 ก โลเมตร ต อ 10 ช วโมงต อว น [9] ป ณยน ช เสนอป ญหาการเด นทางของพน กงานขายเม อม ข อจาก ดด าน การเต มเช อเพล ง โดยใช ป ญหาการเด นทางของพน กงานขาย (Travelling Salesman Problems: TSP) ในการแก ป ญหา งานว จ ยท เก ยวข องป ญหาการเด นทางของพน กงานขาย (Travelling Salesman Problems: TSP) เป นการหาล าด บของ การเด นไปย งสถานท ต างๆท กสถานท โดยไปเพ ยงสถานท ละ หน งคร งแล วเด นทางกล บมาย งสถานท เร มต นซ งเป นเร องยาก ของป ญหา TSP ค อเม อขนาดของจ านวนสถานท เพ มมากข น ล าด บการเด นไปย งสถานท ต างๆท เป นไปได ก จะม จ านวนมาก ข นจากหลายๆงานว จ ยของป ญหาน ได ใช ว ธ ท แตกต างก นใน การแก ป ญหาได แก ว ธ กราฟ (Grape), ว ธ อาณาน คมมด(AC), ว ธ Genetic Ordinal Optimization (GOO), ว ธ Tabu Search และ ว ธ ฮ วร สต กอ นๆเป นต น อ ลกอร ท ม (Algorithm) หมายถ ง ข นตอนหร อล าด บการประมวลผลในการแก ป ญหาใดป ญหา หน งซ งจะช วยให เห นข นตอนของการเข ยนโปรแกรมง ายข น ร ปแบบป ญหาเส นทางการเด นรถโดยม พ นฐานเร มมาจาก ความต องการท จ ดต างๆและถ กบร การด วยรถขนส งโดยไม ม ข อจ าก ดด านระยะทางและปร มาณป ญหาด งกล าวจะถ ก แก ป ญหาโดยให ม ค าใช จ ายในการขนส งต าส ดและม เส นทาง การเด นรถท เหมาะสมว ธ การแก ป ญหาได ม ผลงานด าน Operation Research ไว มากมายด งน ป ญหาการเด นทางของ พน กงานขาย (Traveling Salesman Problem, TSP) เป นป ญหา เก ยวก บการหาเส นทางระหว างจ ดต างๆโดยม จ ดเร มต นแล ว ค นหาเส นทางท เหมาะสมในการเด นทางไปในแต ละจ ดท ก าหนดแล วกล บมาส จ ดเร มต นด งภาพท 1 ภาพท 1 ผลล พธ ของป ญหาการเด นทางของพน กงานขาย การค นหาเส นทาง การค นหาแบบไบล ด (Blind Search) [9] การค นหาแบบไบล ด เป นการค นหาค าตอบท ม ท ศทางในการ ค นหาจะม การค นหาค าตอบของข อม ลท กต วสามารถแบ งได พฤศจ กายน 2557 เป นการค นหาแบบล ก (Depth first search) และการค นหาแบบ กว าง (Breadth first search) ส าหร บการค นหาแบบล ก เป นการ ค นหาท ก าหนดท ศทางจากร ปของโครงสร างต นไม เร มต นจาก โหนดรากระด บท 0 แล วส ารวจโหนดรากในระด บลองลงมา เร อยๆ จนถ งโหนดท อย ล กท ส ด แล วจ งย อนกล บมาโหนดท อย ส งส ดส ารวจเช นน จนกว าจะครบท กโหนดด งแสดงในภาพท 2 ประสานงานก บล กค าพร อมท งก าหนดล าด บการเด นทางและ เส นทางท ใช ในการเด นทางท เหมาะสม (3) เม อต ดต อล กค า แล วน นต องท าเร องจดระยะการเด นทาง ก าหนดว นเด นทางท แน นอน ในการเด นทางน น บร ษท ม นโยบายให จดก โลเมตร ก อนการเด นทางเพ อให ทราบถ งระยะทางท เด นทางไปพบ ล กค าในแต ละคร งว าม ค าใช จ ายมากหร อน อยเพ ยงใด (4) เม อ พบล กค าเสร จแล วน นอ นด บส ดท ายค อการน ารถส งมอบ กล บค นบร ษ ท เบ กค าใช จ ายในการเด นทางและเบ ยเล ยงส าหร บ พน กงานขายในแต ละว นซ งโดยละเอ ยดแต ละข นตอนน น สามารถอธ บายได ด งภาพท 3 ภาพท 2 การค นหาแบบล ก(Depth first search) 2.ว ธ ว จ ย ส าหร บป ญหาการจ ดเส นทางการเด นทางของพน กงาน กรณ ศ กษา การเด นทางเพ อไปพบล กค าพบว าม ล กค า 41 ราย โดยทร พยากรในบร ษ ทม พน กงานรวมท งส น 7 คน โดยแบ ง การด แลออกเป นภาคกลาง 1 คน และในเขตกร งเทพ 2 คน ใน เขตปร มณฑลและภาคตะว นออก 4 คน ส วนพ นท ต งของล กค า ม ภาคกลางแบ งออกเป นจ งหว ด อย ธยา สระบ ร ลพบ ร ในเขต ความร บผ ดชอบส วนปร มณฑลน นม ล กค าแบ งออกเป น 3 จ งหว ด ปท มธาน สม ทรปราการ นนทบ ร นครปฐมส าหร บใน งานว จ ยน ส งท ผ ท าการว จ ยให ความสนใจค อ ระยะทางในการ เข าพบล กค าโดยจะท าการเก บข อม ล พ นท ต งของบร ษ ทล กค า หล กการเล อกเข าพบล กค าโดยจ าแนกตามว ตถ ประสงค การเข า พบและการจ ดล าด บเส นทางในการเข าพบล กค า ก าหนดให ระยะทางไปกล บเท าก น (Symmetric) อธ บายข นตอนการเด นทางของพน กงานขายในป จจ บ น (1) ส าหร บการเด นทางของพน กงานขายน นโดยเบ องต น ได ม การวางแผนการเด นทางก อนล วงหน าโดยข นตอนน ทาง บร ษ ทได ม การวางแผนให โดยพน กงานจะทราบล วงหน าก อน การเด นทางเป นระยะเวลา 1 อาท ตย แต หากว นไหนม งานท ล กค าต องการให ไปพบด วนเข ามาอาจจะท าการเพ มข อม ลท ต องท าการต ดต อเพ มเต มได (2) ในการเด นทางน นพน กงาน ขายท ร บผ ดชอบในพ นท การด แลจะท าหน าท เป นคน การวางแผนพร อมท งก าหนดบร ษ ทของล กค าท ต องท าการต ดต อ ส าหร บร กษาฐานล กค าและรายการส งเสร มการขายต างๆ ประสานงานการต ดต อก บล กค าโดยก าหนดให พน กงานท านใดท ด แล หน าท เขตพ นท ของล กค าน นเป นคนต ดต อ ก าหนดเส นทางและว นในการเด นทาง พร อมท งอน ม ต รถในการ เด นทางพร อมท งม การจดบ นท กการเด นทาง น ารถส งมอบค นกล บบร ษ ท เบ กค าใช จ ายในการเด นทาง และเบ ยเล ยงส าหร บพน กงานขาย ภาพท 3 ข นตอนการเด นทางของพน กงาน ขายในป จจ บ น ข นตอนการด าเน นการ ข นตอนท 1 ศ กษาเส นทางการเด นทางพร อมท งศ กษาป ญหาท เก ดข น ข นตอนท 2 ก าหนดว ตถ ประสงค ของการด าเน นงานว จ ย พร อมท งก าหนดขอบเขต ข นตอนท 3 ศ กษางานว จ ยและทฤษฎ ท เก ยวข อง ข นตอนท 4 รวบรวมข อม ลเก ยวก บเส นทางการเด นทาง พร อมท งป จจ ยท เก ยวข องในการเด นทาง ข นตอนท 5 ใช ว ธ ป ญหาการเด นทางของพน กงานขาย (Travelling Salesman Problems: TSP) เพ อจ ด เส นทางการเด
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks