ขนาด

ตัวแก้โจทย์การกำหนดเส้นทางใช้ออบเจ็กต์ที่เรียกว่ามิติข้อมูลเพื่อติดตาม ปริมาณที่สะสมบนเส้นทางของยานพาหนะ เช่น เวลาที่ใช้ในการเดินทาง หรือ หากยานพาหนะใช้ขนส่งสินค้าและนำส่ง น้ำหนักรวมที่ใช้บรรทุก ที่ใช้เวลาเพียง 2 นาที ถ้าปัญหาการกำหนดเส้นทางเกี่ยวข้องกับจำนวนดังกล่าว ทั้งในข้อจำกัดหรือ ฟังก์ชันวัตถุประสงค์ คุณจะต้องกำหนดมิติข้อมูลเพื่อระบุมิติข้อมูล

ส่วนนี้จะอธิบายวิธีกำหนดและใช้มิติข้อมูล

ตัวอย่างของมิติข้อมูล

ต่อไปนี้เป็นตัวอย่างมิติข้อมูล 2-3 ข้อจากส่วนก่อนหน้า

• ตัวอย่าง VRPTW สร้างมิติข้อมูลเพื่อติดตาม ระยะเวลาเดินทางสะสมของยานพาหนะแต่ละคัน เครื่องมือแก้โจทย์ใช้มิติข้อมูลเพื่อบังคับใช้ ข้อจำกัดที่ว่ายานพาหนะสามารถเข้าชมได้เฉพาะสถานที่ภายใน กรอบเวลา

• ตัวอย่าง CVRP จะสร้างมิติข้อมูลสำหรับ ความต้องการ (เช่น น้ำหนักหรือปริมาณบรรจุภัณฑ์ที่จะรับ) ซึ่งติดตาม น้ำหนักบรรทุกสะสมที่พาหนะใช้อยู่บนเส้นทาง เครื่องมือแก้โจทย์คณิตใช้มิติข้อมูลเพื่อบังคับใช้ข้อจำกัดเกี่ยวกับน้ำหนักบรรทุกของยานพาหนะ ต้องไม่เกินจากความจุ

ตัวอย่างด้านล่างกำหนดมิติข้อมูลสำหรับ VRPTW โดยใช้ AddDimension

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

เมธอด AddDimension มีอินพุตต่อไปนี้

• callback_index: ดัชนีสำหรับ Callback ที่แสดงจำนวน ดัชนี ซึ่งเป็นการอ้างอิงภายในของตัวแก้โจทย์กับ Callback จะสร้างขึ้นโดย เช่น RegisterTransitCallback หรือ RegisterUnitaryTransitCallback
• slack_max: ค่าสูงสุดสำหรับ slack ซึ่งเป็นตัวแปรที่ใช้แทนการรอ ในสถานที่ต่างๆ โปรดดูตัวแปร Slack ด้านล่างสำหรับ รายละเอียด หากปัญหาไม่จำเป็นต้องมีเวลารอ คุณก็มักจะตั้งค่า slack_max ได้ เป็น 0
• capacity: ค่าสูงสุดสำหรับปริมาณทั้งหมดสะสมตลอดเส้นทางแต่ละเส้นทาง ใช้ capacity เพื่อสร้างข้อจำกัดแบบเดียวกับที่มีอยู่ใน CVRP ถ้าปัญหาของคุณไม่มี คุณสามารถตั้งค่า capacity เป็นค่าที่ใหญ่พอที่จะ ไม่มีข้อจำกัดเกี่ยวกับเส้นทาง เช่น ผลรวมของทุกเส้นทาง ของเมทริกซ์หรืออาร์เรย์ที่ใช้กำหนด Callback
• fix_start_cumulative_to_zero: ค่าบูลีน หากจริง ค่าสะสม ของจำนวนเริ่มต้นที่ 0 ในกรณีส่วนใหญ่ ควรตั้งค่านี้เป็น True แต่สำหรับ VRPTW หรือปัญหาเกี่ยวกับ ข้อจำกัดด้านทรัพยากร ยานพาหนะบางคัน อาจต้องเริ่มต้นหลังจากเวลา 0 เนื่องจากข้อจำกัดด้านกรอบเวลา คุณจึงควร ตั้งค่า fix_start_cumulative_to_zero เป็น False สำหรับโจทย์เหล่านี้
• dimension_name: สตริงสำหรับชื่อของมิติข้อมูล เช่น 'Distance' ซึ่งคุณสามารถใช้เพื่อเข้าถึงตัวแปรต่างๆ ในโปรแกรม

โปรแกรม CVRP จะสร้างมิติข้อมูลประเภทที่แตกต่างกันเล็กน้อยโดยใช้ AddDimensionWithVehicleCapacity วิธีการนี้รองรับความจุหลากหลาย โดยมี 1 รายการสำหรับยานพาหนะแต่ละคัน (ในทางตรงกันข้าม AddDimension จะใช้ค่าเดียวสำหรับ capacity ดังนั้น โดยให้ถือว่ามีความจุเท่ากัน)

โปรดดูRoutingModel สำหรับวิธีการอื่นๆ ที่สร้างมิติข้อมูล

ส่วน บันทึกกรอบเวลาของโซลูชันลงในรายการหรืออาร์เรย์ แสดงฟังก์ชันที่บันทึกข้อมูลสะสมในมิติข้อมูลในรายการหรืออาร์เรย์

ตัวแปรของ Slack

ด้านล่างนี้เป็นตัวอย่างที่แสดงให้เห็นตัวแปร Slack สำหรับปัญหาที่เกี่ยวข้องกับ ระยะเวลาเดินทาง สมมติว่า ยานพาหนะแล่นจากตำแหน่ง i ไปยังตำแหน่ง j ในขั้นตอนใดขั้นตอนหนึ่งของเส้นทาง และ

• ระยะเวลาเดินทางสะสมของยานพาหนะที่ i คือ 100 นาที
• ระยะเวลาเดินทางสะสมของยานพาหนะที่ j คือ 200 นาที
• เวลาเดินทางจาก i ไป j คือ 75 นาที

รถไม่สามารถออกจากตำแหน่งได้ในทันทีเมื่อมาถึงหรือสะสมอยู่ เวลาที่สถานที่ j จะเป็น 175 แต่จะต้องรอเป็นเวลา 25 นาทีที่ สถานที่ i ก่อนออกเดินทาง พูดอีกอย่างคือ ตำแหน่งที่ไม่ปกติ i อายุ 25 ปี

คุณต้องอนุญาตให้รถหย่อนลงใน VRPTW เนื่องจากยานพาหนะอาจต้องรอก่อน เยี่ยมชมสถานที่เนื่องจากข้อจำกัดด้านเวลา ในโจทย์แบบนี้ ให้ตั้งค่า slack_max เป็นระยะเวลาสูงสุดที่คุณต้องการอนุญาตให้ยานพาหนะรอ ก่อนไปที่ตำแหน่งถัดไป หากไม่สำคัญว่าใช้เวลาเท่าใด ก็แค่ตั้งค่า slack_max ให้มีตัวเลขจำนวนมากเลย

ในทางกลับกัน สำหรับ CVRP การเปลี่ยนแปลงของโหลดสะสมจาก i เป็น j จะเท่ากับความต้องการที่ i เสมอ จึงไม่มีความหลวม สำหรับปัญหา เช่น ตัวเลือกนี้ตั้งค่า slack_max เป็น 0 ได้

ถัดไป เราจะให้คำจำกัดความอย่างเป็นทางการของ Slack ตัวเลือกภายใน ที่เก็บมิติข้อมูล ตัวแปร 2 ประเภทที่เกี่ยวข้องกับปริมาณที่สะสมตามเส้นทาง ได้แก่

• ตัวแปรขนส่งสาธารณะ: การเพิ่มขึ้นหรือลดลงของปริมาณในแต่ละขั้นตอนของ เส้นทาง ถ้า i -> j คือขั้นตอนเดียวในเส้นทาง ตัวแปรการขนส่งจะเป็น i j ของเมทริกซ์การขนส่งสาธารณะ (สำหรับการเรียกกลับของการขนส่งสาธารณะ) หรือเรียกง่ายๆ ว่า ค่า Callback ที่ตำแหน่ง i (หาก Callback ขึ้นอยู่กับสถานที่ตั้งเพียงแห่งเดียว)
• ตัวแปรสะสม: ปริมาณสะสมทั้งหมดของสถานที่แต่ละแห่ง คุณ สามารถเข้าถึงตัวแปรสะสมในตำแหน่ง i โดย dimension_name.CumulVar(i) ตัวอย่างเช่น ดูที่ ข้อจำกัดด้านกรอบเวลา ในตัวอย่าง VRPTW

สมมติว่ายานพาหนะเดินทางจากตำแหน่ง i ไปยังตำแหน่ง j ในขั้นตอนเดียว slack เกี่ยวข้องกับตัวแปรเหล่านี้ดังนี้

slack(i) = cumul(j) - cumul(i) - transit(i, j)

ดูรายละเอียดเพิ่มเติมเกี่ยวกับมิติข้อมูลได้ที่ RoutingDimension ในส่วนการอ้างอิง