ต วแบบทางคณ ตศาสตร สาหร บปร บสมด ลงานในป ญหาการเด นทางของพน กงานขาย กรณ หลายคนด วยหล กการค าน อยส ดของค ามากส ด - PDF

Description
ต วแบบทางคณ ตศาสตร สาหร บปร บสมด ลงานในป ญหาการเด นทางของพน กงานขาย กรณ หลายคนด วยหล กการค าน อยส ดของค ามากส ด บทค ดย อ อภ ศ กด ว ทยาประภากร *1 มหาว ทยาล ยพะเยา 19 หม 2 ตาบลแม กา อาเภอเม อง จ งหว ดพะเยา

Please download to get full document.

View again

of 18
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:

Fan Fiction

Publish on:

Views: 11 | Pages: 18

Extension: PDF | Download: 0

Share
Transcript
ต วแบบทางคณ ตศาสตร สาหร บปร บสมด ลงานในป ญหาการเด นทางของพน กงานขาย กรณ หลายคนด วยหล กการค าน อยส ดของค ามากส ด บทค ดย อ อภ ศ กด ว ทยาประภากร *1 มหาว ทยาล ยพะเยา 19 หม 2 ตาบลแม กา อาเภอเม อง จ งหว ดพะเยา และ พ รย ทธ ชาญเศรษฐ ก ล 2 มหาว ทยาล ยเกษตรศาสตร 50 แขวงลาดยาว เขตจต จ กร กร งเทพมหานคร งานว จ ยช นน ได นาเสนอต วแบบส าหร บการปร บสมด ลระยะการเด นทางในป ญหาการเด นทางของพน กงานขายกรณ หลายคนท งหมด 2 ต วแบบ โดยอาศ ยหล กการค าน อยส ดของค ามากส ด ซ งต วแบบท 1 เป นต วแบบทางคณ ตศาสตร ท ม จานวน ต วแปรท งหมด (m+1) 2 +1 ต ว โดยท m เป นจ านวนของพน กงานขาย และ เป นจ านวนสถาน โดยค าตอบท ได จะเป น ค าตอบท ไม เก ดท วร ย อย ส วนต วแบบท 2 เป นต วแบบการจ าลองหาค าตอบผ านฟ งก ช น Evolutioary ในโปรแกรม Excel Solver เพ อรองร บการหาคาตอบในกรณ ท ป ญหาม ขนาดใหญ โดยม ต วแปรท งหมด m+-2 ต ว เพ ยงแต คาตอบท ได จะไม การ น ต ว าจะเป นค าท ด ท ส ด ซ งท ง 2 ต วแบบจะม ข นตอนการหาคาตอบท เหม อนก นค อ ข นท 1 เป นการใช หล กการค าน อยส ดของค า มากส ดเพ อค นหาค าท น อยท ส ดของพน กงานท ม การเด นทางมากท ส ดก อน ส วนข นท 2 เป นการปร บให ระยะทางรวมม ค าน อย ท ส ดเท าท เป นไปได โดยอาศ ยการนาคาตอบจากข นตอนท 1 มากาหนดเป นขอบเขตบนของระยะการเด นทางในพน กงานท กๆ คน แล วหาคาตอบ คาสาค ญ: ป ญหาการเด นทางของพน กงานขายหลายคน, ค าน อยส ดของค ามากส ด, การกาจ ดท วร ย อย, จ ดสมด ลระยะทาง * Correspodig author อาจารย สาขาว ศวกรรมอ ตสาหการ คณะว ศวกรรมศาสตร มหาว ทยาล ยพะเยา 2 รองศาสตราจารย ภาคว ชาว ศวกรรมอ ตสาหการ คณะว ศวกรรมศาสตร มหาว ทยาล ยเกษตรศาสร 13 A Mathematical Model for Balacig the Work Load of Multiple Travelig Salesma Problem Usig the Miimax Theorem Abstract Apisak Vittayaprapakor *1 School of Egieerig, Uiversity of Phayao, 19 Moo 2 Tambo Maeka Amphur Muag Phayao ad Peerayuth Charsethikul 2 Faculty of Egieerig, Kasetsart Uiversity, 50 Ngam Wog Wa Road Ladyaow Chatuchak Bagkok This research aims to preset two models for balacig distace i the case of multiple travelig salesma problem (mtsp), by applyig the Miimax theorem as the fudametal framework. The first is the mathematical model i which all variables hold that (m+1) 2 +1, give m for salesme ad for statios. As a result of the first model, the aswer obtaied did ot cause sub-tour. The secod is a simulatio model, which simulates aswer through the Evolutioary fuctio i Microsoft Excel Solver i order to solve large- scale problems. Havig all of the variables as m+-2, ad accordig to the results we foud, however, does ot guaratee as the optimizatio. It was foud i this study that both models had the same steps i fidig the aswer; the first step was by applyig the Miimax theorem for fidig the miimum value from the salesma that travelled the logest distace. The secod step was by miimizig the total distace by takig the aswer from the first step to be set as the upper boud of all salesme s distaces ad the fid the aswer. Keywords: multiple travelig salesma problem, Miimax, sub-tour elimiatio, distace balacig * Correspodig author Lecturer i School of Egieerig, Uiversity of Phayao 2 Associate Professor i Faculty of Egieerig, Kasetsart Uiversity 14 1. บทนา ในอด ตท ผ านมาการสร างต วแบบทางคณ ตศาสตร ส าหร บป ญหาการเด นทางของพน กงานขายกรณ พน กงาน หลายคน จะเป นการต งเป าหมายให ระยะการเด นทางรวม ของพน กงานท กคนส นท ส ดเป นหล ก ท าให การกระจายภาระ งานหร อระยะทางของพน กงานแต ละคนอาจจะไม สมด ลก น ซ งเก ดป ญหาในความเป นจร งเพราะการท างานจร งพน กงาน ท กคนควรจะร บท เท าๆก น พร อมท งระยะทางก ควร จะน อยเท าท เป นไปได จากป ญหาท ได กล าวมาท าให ผ ว จ ยม แนวความค ดท จะสร างต วแบบทางคณ ตศาสตร ส าหร บแก ไขป ญหาการ เด นทางของพน กงานขายกรณ พน กงานหลายคน โดยม งเน น ไปท การกระจายงานต องสมด ลและระยะทางรวมก ต องน อย ท ส ดเท าท จะเป นไปได เพ อให เหมาะสมก บความเป นจร ง มากกว าต วแบบทางคณ ตศาสตร ท เคยม มา งานว จ ยช นน ได ท าการทดลองประมวลผลหาค า ตอบของต วแบบทางคณ ตศาสตร ผ าน Gurobi Solver [1] เน องจากได ม การทดสอบเปร ยบเท ยบหาประส ทธ ภาพและ ประส ทธ ผลในป 2013 โดย Berhard Meidl พบว าเป น ซอฟต แวร ส าหร บการประมวลผลหาค าตอบส าหร บต วแบบ ทางคณ ตศาสตร ประเภท Mix Iteger Programmig ท ม ประส ทธ ภาพและประส ทธ ผลท ส ง[2] เม อเท ยบก บซอฟต แวร ประมวลผลชน ดต างๆ โดยผลค าตอบท ได จะถ กน ามา เปร ยบเท ยบก บค าตอบท ได ต วแบบทางคณ ตศาสตร ของ Datzig เพ อด ว าม การกระจายของท ด ข นหร อไม นอกจากน นแล วในส วนของงานว จ ยย งได นาเสนอต วแบบการ จาลองหาคาตอบสาหร บฟ งก ช น Evolutioary ในโปรแกรม Excel Solver ส าหร บบ คคลท วไปสามารถน าไปประย กต ใช งานเพ อหาคาตอบข นต นได 2. ทฤษฎ และงานว จ ยท เก ยวข อง ป ญหาการเด นทางของพน กงานขายหลายคน (mtsp) เป นป ญหาท ขยายข นมาจากป ญหาการเด นทางของ พน กงานขายคนเด ยว (TSP) โดยร ปแบบของป ญหา เป นการ หาเส นทางการส งส นค าของพน กงานขายมากกว า 1 คนให ม ระยะการเด นทางรวมน อยท ส ด โดยม เง อนไขด งต อไปน ค อ ต องเด นทางส งส นค าให ครบท กจ ดร บส นค า, จ ดร บส นค าจะม การร บส นค าแค 1 คร ง, พน กงานขายจะไม ไปส งส นค าท จ ด เด ยวก น และพน กงานขายม จ ดต งต นและจ ดส ดท ายของการ เด นทางค อคล งส นค า [3] [4] โดยม ประว ต การว จ ยสาค ญ เก ยวก บการสร างต วแบบทางคณ ตศาสตร ร ปแบบต างๆ ด งต อไปน ในป 1954 Datzig ได ม การสร างต วแบบทาง คณ ตศาสตร ส าหร บหาค าตอบ ซ งต วแบบจะม ร ปแบบเป น Iteger Programig โดยม การต งเป าหมายให ม ระยะทาง รวมส นท ส ด และจะต องม การเพ มเง อนไขก าจ ดท วร ย อย จนกว าคาตอบท ได จะไม ม ท วร ย อย [5] เพ อก าจ ดป ญหาท วร ย อย จ งได ม การสร างเง อนไข เพ อกาจ ดป ญหาท วร ย อยในป 1960 โดย Miller ซ งเง อนไขท เพ มข นมาจะม ต วแปรท เร ยกว า ode potetials (ต วแปร u) เป นต วแปรท ม ค าเป นจ านวนจร งและมากกว าหร อเท าก บ ศ นย ทาให ต วแบบท เพ มเง อนไขน เข าไปจะม ร ปแบบเป น Mix Iteger Programig นอกจากน นแล วย งสามารถก าหนด ขอบเขตบนของจานวนเม องท จะเด นทางผ านค า p ในสมการ เง อนไขได อ กด วย [6] ในส วนการสร างเง อนไขก าจ ดป ญหาท วร ย อยก ม การ น าเสนอเพ มเต มโดย Gavish ในป 1976 ซ งหล กการจะ เหม อนก บเง อนไขของ Miller เพ ยงแต เปล ยนจากค า p เป น -m โดยให ค า ค อจ านวนเม อง และ m ค อจ านวนของ พน กงานขาย โดยท m ม ค ามากกว าหร อเท าก บ 2 [7] ในป 1980 Laporte และ Nobert ได น าเสนอต ว แบบทางคณ ตศาสตร กรณ เพ มเง อนไขค าต นท นคงท เข ามา โดยต วแบบท น าเสนอน นจะแบ งออกเป น 2 ต วแบบค อ ร ปแบบสมมาตร และร ปแบบไม สมมาตร [8] ในป 1985 Kulkari ก ได ม การน าเสนอต วแบบทาง คณ ตศาสตร ท เพ มเง อนไขม คล งส นค ามากกว า 1 แห ง โดย แบ งออกเป น 2 ต วแบบค อ ร ปแบบท จ ดต งต นก บจ ดส ดท าย ของการเด นทางไม จ าเป นต องเป นจ ดเด ยวก น และร ปแบบท จ ดต งต นก บจ ดส ดท ายต องเป นจ ดเด ยวก น [9] ต อมาในป 2004 Kara และ Bektas ได ม การ ด ดแปลงเง อนไขก าจ ดท วร ย อยของ Miller ให สามารถ กาหนดขอบเขตล าง ของจานวนเม องท จะเด นทางได [10] จากงานว จ ยเช งต วแบบทางคณ ตศาสตร ท ผ านมาน น จะเห นได ว าไม ม งานว จ ยช นไหนท าการสร างต วแบบทาง คณ ตศาสตร ส าหร บกระจายงานให พน กงานขายกรณ หลาย คนให ม ความสมด ลเลย จ งท าให ผ ว จ ยม แนวความค ดท จะ สร างต วแบบข นมาโดยเน นไปท การจ ดสมด ลให พน กงานขาย พร อมท งให ม ระยะทางรวมน อยท ส ดเท าท เป นไปได จากแนวความค ดด งกล าวทางผ ว จ ยจ งท าการศ กษา ค นคว างานว จ ยท เก ยวก บการกระจายระยะการเด นทางของ 15 พน กงานขายนอกจากร ปแบบท เป นต วแบบทาง คณ ตศาสตร พบว าม งานว จ ยของ Xu Hog-li ซ งว จ ยในป 2009 ท คล ายก บแนวค ดของผ ว จ ย โดยงานว จ ยจะเป นการ นาเสนอการกระจายโดยม เป าหมาย 2 เป าหมายค อ กระจายจ านวนเม องท ต องเด นทาง และจ ดสมด ลระยะทาง โดยใช Hybrid Algorithm เป นเคร องม อค นหาค าตอบ[11] ซ งต างจากงานของผ ว จ ยท ต องการเน นไปในส วนของการจ ด สมด ลระยะทางโดยไม ได พ จารณาในส วนของจ านวนเม องท ต องเด นทาง ส วนว ธ การค นหาค าตอบเป นการใช ต วแบบทาง คณ ตศาสตร และน าเสนอการประย กต ใช ฟ งก ช น Evolutioary ของโปรแกรม Excel เพ มเต มด งน นจ งกล าว ได ว าเป นงานว จ ยช นแรกท ได ค นคว ามาในแนวทางของการ จ ดสมด ลเส นทางผ านการใช ต วแบบทางคณ ตศาสตร และ ประย กต ใช ฟ งช นก Evolutioary ของ Excel Solver ใน การจ ดสมด ลระยะทาง ในการส วนของการเปร ยบเท ยบผลคาตอบผ ว จ ยจะใช ต วแบบทางคณ ตศาสตร พ นฐานของ Datzig มาประมวลผล หาค าตอบเปร ยบเท ยบในเร องของการกระจาย และระยะทางท เพ มข น โดยต วแบบของ Datzig แสดงได ด งต อไปน ต วแปรท ใช x ij = ต วแปรต ดส นใจส าหร บเล อกหร อไม เล อกจากจ ด i ไปย งจ ด j (i เป นด ชน แสดงจ ดท พน กงานขายเด นทางออก และ j เป นด ชน แสดงจ ดท พน กงานขายเด นทางเข า) โดยม ค า เป น 0,1 c ij = ระยะทางจากจ ด i ไปจ ด j = จานวนจ ดร บส นค ารวมก บคล งส นค า m = จานวนของพน กงานขาย S = จานวนจ ดท ม ร ปแบบเซ ตค าตอบเป นท วร ย อยซ งไม เช อมต อก บจ ดต งต น V = เซ ตของจ ดร บส นค า สมการเป าหมาย Miimize cx ij ij (1) i 1 j 1 ค อ การต งให เป าหมายม ระยะทางรวมท ส นท ส ด ภายใต เง อนไข x1 j m (2) j 2 ค อ การกาหนดให จ ดคล งส นค าต องม พน กงานขาย เด นทางออกเป นจานวน m xj1 m (3) j 2 ค อ การกาหนดให จ ดคล งส นค าต องม พน กงานขาย เด นทางกล บเข ามาเป นจานวน m xij 1 สาหร บ j, j 2 i 1 (4) ค อ การให จ ดร บส นค าแต ละจ ดม การเด นทางออกได เพ ยง 1 คร ง xij 1 สาหร บ i,i 2 j 1 (5) ค อ การให จ ดร บส นค าแต ละจ ดม การเด นทางเข าได เพ ยง 1 คร ง xij S 1, S V\ 1, S (6) i S j S ค อ สมการท ใช สาหร บการกาจ ดท วร ย อยท เก ดข น ส าหร บการสร างต วแบบทางคณ ตศาสตร เพ อจ ด สมด ลการเด นทาง ผ ว จ ยได ศ กษาเทคน คการสร างต วแบบ ทางคณ ตศาสตร จากหน งส อModel buildig i mathematical programmig 5 th editio ท าให ทราบถ ง ว ธ การประย กต ใช หล กการของ Miimax เพ อใช จ ดสมด ล ผ านต วแบบทางคณ ตศาสตร [12] นอกจากน นแล ว เพ อให ต วแบบทางคณ ตศาสตร ท สามารถก าหนดเป าหมาย 2 เป าหมายได พร อมๆ ก น ค อการกระจายงานต องสมด ลและ ระยะทางรวมก ต องน อยท ส ดเท าท จะเป นไปได ท าให ทาง ผ ว จ ยต องไปศ กษาเพ มเต มในส วนของทฤษฎ Goal Programmig ซ งเป นว ธ การหาค าตอบส าหร บต วแบบทาง คณ ตศาสตร ในกรณ ท ม เป าหมายมากกว า 1 เป าหมายข นไป จาก หน งส อสร างแบบจ าลองเ พ อการต ดส นใจ Optimizatio Modelig ด วย Excel (Solver) [13] และ หน งส อ Spreadsheet Modelig & Decisio Aalysis Sixth Editio [14] ในบทของ Goal Programmig พบว า การก าหนด 2 เป าหมายน นสามารถท าได หลายว ธ แต ว ธ ท ผ ว จ ยได น ามาใช ค อการก าหนดเป าหมา
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