The Capacitated Vehicle Routing Pro

The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization problem in transportation logistics and distribution systems of considerable economic significance, was first introduced by Dantzig and Ramser (1959), then extensively studied in the literature in various versions and approached using alternative algorithms.

The problem consists, in its basic version, of designing a set of minimum cost-routes for a number of identical vehicles having a fixed capacity to serve a set of customers with known demands. Several structural constraints can be added to the basic CVRP giving rise to many variants such as time windows for the customer to be served, limits on the lengths of the routes and limits on the time that a driver can work.

Since the CVRP is a NP-hard problem, three solution approaches are typically employed: heuristics, approximation and exact methods (Alba and Dorronsoro, 2006 and Osman, 1993). Only instances of small size can be solved to optimality using exact solution methods. While heuristics do not provide guarantees about the solution quality, they are useful in practical contexts thanks to their speed and ability to handle giant instances. An approximation algorithm is a special class of heuristics that provide a solution and an error guarantee.

We show through the present study the powerfulness of linking GIS with optimization tools to solve routing problems. Our DSS integrates Google Maps and the TS metaheuristic for the loading-routing problem modeled as a CVRP. The proposed tool firstly inputs the basic parameters of the problem then, extracts spatial information from the geographical database (GDB). The numerical solution obtained by applying a TS is plotted on a map and commented by providing a detailed report on the proposed scenario. The parametrization of the solution approach is discussed in order to output the near-optimal solution that coincides with the decision maker’s preferences. To check the validity of the proposed DSS, we address a real case study in the city of Jendouba (Tunisia).

This paper is structured as follows. The CVRP is described and stated mathematically in Section 2. In Section 3, the main steps of the proposed DSS are outlined and described. The TS metaheuristic that generates the numerical solution of the DSS, enhanced by neighborhood techniques, is detailed in Section 4. Experimental results within the region of Jendouba (Tunisia) are reported in Section 5.

ผลลัพธ์ (ไทย) 1:

Capacitated รถสายปัญหา (CVRP), ปรับพื้นฐานปัญหาปัญหาในระบบโลจิสติกส์และกระจายสินค้าการขนส่งของความสำคัญทางเศรษฐกิจมาก ถูกนำมาใช้ครั้งแรกโดย Dantzig Ramser (1959), อย่างกว้างขวางศึกษาวรรณคดีในรุ่นต่าง ๆ แล้วประดับโดยใช้อัลกอริทึมอื่นปัญหาประกอบด้วย ในรุ่นของพื้นฐาน ออกแบบชุดของเส้นทางต้นทุนต่ำสุดสำหรับคันเหมือนกันมีความจุคงให้บริการชุดของลูกค้า มีความต้องการทราบ สามารถเพิ่มข้อจำกัดโครงสร้างหลายพื้นฐาน CVRP ให้เพิ่มขึ้นไปหลายสายพันธุ์เช่นหน้าต่างเวลาสำหรับลูกค้าการให้บริการ ข้อจำกัดในความยาวของเส้นทางและจำกัดเวลาที่โปรแกรมควบคุมสามารถทำงานCVRP เป็น ปัญหายาก NP, 3 วิธีแก้ปัญหาโดยทั่วไปพนักงาน: ประมาณ ลองผิดลองถูก และวิธีที่แน่นอน (อัลบา และ Dorronsoro, 2006 และ Osman, 1993) อินสแตนซ์ของขนาดเล็กสามารถแก้ไขการ optimality ใช้วิธีแก้ปัญหาที่แน่นอน ในขณะที่ลองผิดลองถูกให้ประกันเกี่ยวกับคุณภาพแก้ปัญหา จะมีประโยชน์ในบริบทปฏิบัติการความเร็วและความสามารถในการจัดการกับอินสแตนซ์ยักษ์ อัลกอริทึมการประมาณเป็นชั้นพิเศษของการลองผิดลองถูกที่ให้แก้ไขปัญหาและการรับประกันข้อผิดพลาดเราแสดงผ่านการศึกษาปัจจุบัน powerfulness ของเชื่อมโยง GIS มีเครื่องมือเพิ่มประสิทธิภาพการแก้ปัญหากระบวนการผลิต ของ DSS รวม Google Maps และ TS metaheuristic ปัญหาการโหลดเส้นทางที่จำลองเป็น CVRP เป็น เครื่องมือการนำเสนอประการแรก inputs พารามิเตอร์พื้นฐานของปัญหา นั้น แยกพื้นที่ข้อมูลจากฐานข้อมูลทางภูมิศาสตร์ (GDB) โซลูชันตัวเลขที่ได้รับ โดยใช้ TS ลงจุดบนแผนที่ และแสดงความคิดเห็น โดยให้รายงานโดยละเอียดเสนอสถานการณ์ Parametrization วิธีแก้ปัญหาจะกล่าวถึงเพื่อแสดงผลการแก้ปัญหาใกล้ดีที่สุดที่กรุณากำหนดลักษณะการตัดสินใจของ การตรวจสอบถูกต้องของ DSS เสนอ เรากรณีศึกษาจริงเมืองของ Jendouba (ตูนิเซีย)กระดาษนี้มีโครงสร้างดังนี้ CVRP ที่อธิบาย และระบุ mathematically ใน 2 ส่วน ใน 3 ส่วน ขั้นตอนหลักของ DSS เสนอจะอธิบาย และอธิบาย TS metaheuristic ที่สร้างโซลูชันตัวเลขของ DSS ด้วยเทคนิคใกล้เคียง มีรายละเอียดใน 4 ส่วน มีรายงานผลการทดลองภายในภูมิภาคของ Jendouba (ตูนิเซีย) ใน 5 ส่วน

ผลลัพธ์ (ไทย) 3:

การ capacitated ปัญหาการจัดเส้นทางยานพาหนะ ( cvrp ) , พื้นฐานการเพิ่มประสิทธิภาพปัญหาโลจิสติกส์ การขนส่งและการกระจายสินค้าระบบความสำคัญทางเศรษฐกิจมากเป็นครั้งแรก โดย แดนท์ซิก และ ramser ( 1959 ) จากนั้นศึกษาอย่างกว้างขวางในวรรณคดี ในรุ่นต่าง ๆ และเดินโดยใช้กลไกทางเลือก

ปัญหาประกอบด้วยในรุ่นพื้นฐานของการออกแบบชุดของเส้นทางค่าใช้จ่ายขั้นต่ำสำหรับจำนวนของยานพาหนะมีความสามารถเหมือนกันคงที่เพื่อให้ชุดของลูกค้าทราบความต้องการ ข้อจำกัดของโครงสร้างหลายสามารถเพิ่มฐาน cvrp ให้สูงขึ้นไปหลายตัวแปรเช่น Windows เวลาสำหรับลูกค้าที่จะให้บริการ , ขีด จำกัด บนความยาวของเส้นทางและกำหนดเวลาที่คนขับสามารถทำงาน

ตั้งแต่ cvrp เป็น NP ยากปัญหาสามโซลูชั่นวิธีการมักจะใช้ : อักษร การประมาณค่าและวิธีการที่แน่นอน ( และ dorronsoro 2006 และอุสมาน , 1993 ) กรณีเฉพาะของขนาดเล็กที่สามารถแก้ไขได้เพื่อคุณภาพโดยใช้วิธีการแก้ปัญหาที่ถูกต้อง ในขณะที่การวิเคราะห์พฤติกรรมที่ไม่ได้ให้การรับรองคุณภาพโซลูชั่นพวกเขาจะเป็นประโยชน์ในบริบทจริงขอบคุณของความเร็วและความสามารถในการจัดการกับกรณียักษ์ การสร้างคลาสพิเศษของฮิวริสติกที่ให้โซลูชั่นและข้อผิดพลาดรับประกัน

เราแสดงผ่านปัจจุบันศึกษา powerfulness ของการเชื่อมโยงระบบสารสนเทศภูมิศาสตร์ด้วยเครื่องมือเพิ่มประสิทธิภาพการแก้ปัญหาระบบสนับสนุนการตัดสินใจ ของเรารวม Google Maps และเมตาฮิวริ ิก เป็นปัญหาการจัดเส้นทางสำหรับการโหลดแบบ cvrp . เสนอเครื่องมือประการแรกกระผมพารามิเตอร์พื้นฐานของปัญหาแล้ว สารสกัดจากข้อมูลเชิงพื้นที่จากฐานข้อมูลทางภูมิศาสตร์ ( Name ) ตัวเลขที่ได้โดยการใช้โซลูชั่น TS เป็นพล็อตบนแผนที่และแสดงความเห็นโดยให้รายงานรายละเอียดเกี่ยวกับการเสนอสถานการณ์และ parametrization ของโซลูชั่นการสนทนาเพื่อที่จะออกโซลูชั่นที่เหมาะสมสอดคล้องกับการตั้งค่าที่ใกล้ตัดสินใจ . เพื่อตรวจสอบความถูกต้องของการเสนอระบบสนับสนุนการตัดสินใจ , เราที่อยู่จริง กรณีศึกษาในเมือง jendouba ( ตูนิเซีย ) .

กระดาษนี้มีโครงสร้างดังนี้ การ cvrp อธิบายและระบุทางคณิตศาสตร์ในส่วนที่ 2 ในมาตรา 3ขั้นตอนหลักของการเสนอระบบสนับสนุนการตัดสินใจจะถูกระบุไว้ และอธิบาย TS เมตาฮิวริ ิกที่สร้างผลเฉลยเชิงตัวเลขของระบบที่เพิ่มขึ้น โดยเทคนิคนี้มีรายละเอียดในส่วนที่ 4 การทดลองภายในภูมิภาคของ jendouba ( ตูนิเซีย ) มีรายงานในส่วนที่ 5 .