ขนาด

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

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

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

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

  • ตัวอย่าง 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: ดัชนีสําหรับโค้ดเรียกกลับที่แสดงจํานวน ดัชนีซึ่งเป็นการอ้างอิงภายในของเครื่องมือแก้โจทย์เพื่อสร้างการเรียกกลับนั้นสร้างขึ้นด้วยเมธอด เช่น RegisterTransitCallback หรือ RegisterUnitaryTransitCallback
  • slack_max: ค่าสูงสุดสําหรับสลาก ซึ่งเป็นตัวแปรที่ใช้แสดงถึงเวลารอที่สถานที่ตั้ง ดูรายละเอียดได้ที่ตัวแปร Slack ด้านล่าง หากปัญหาไม่เกี่ยวข้องกับเวลารอ โดยปกติคุณตั้งค่า slack_max เป็น 0 ได้
  • capacity: จํานวนสูงสุดสําหรับปริมาณสะสมแต่ละรายการในแต่ละเส้นทาง ใช้ capacity เพื่อสร้างข้อจํากัดอย่างใน CVRP หากปัญหาไม่มีข้อจํากัดดังกล่าว ให้ตั้งค่า capacity เป็นค่าที่ใหญ่พอที่จะไม่มีข้อจํากัดเส้นทาง เช่น ผลรวมทั้งหมดของเมทริกซ์หรืออาร์เรย์ที่ใช้กําหนดการเรียกกลับ
  • 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

ต่อไปนี้คือตัวอย่างที่แสดงตัวแปร "ช้า" สําหรับปัญหาที่เกี่ยวข้องกับเวลาในการเดินทาง สมมติว่ารถเคลื่อนที่จากตําแหน่ง i ไปยังตําแหน่ง j ในขั้นตอนหนึ่งของเส้นทาง และ

  • เวลาในการเดินทางสะสมของรถที่ 1 คือ 100 นาที
  • เวลาเดินทางรวมที่ j คือ 200 นาที
  • เวลาเดินทางจาก i ถึง j คือ 75 นาที

ยานพาหนะทิ้งตําแหน่ง i ทันทีเมื่อมาถึงไม่ได้ หรือเวลาสะสมของยานพาหนะที่ตําแหน่ง j จะเท่ากับ 175 แต่ยานพาหนะดังกล่าวต้องรอ 25 นาที ที่สถานที่ i จึงจะออกเดินทาง กล่าวคือ การขับขี่ที่สถานที่ i คือ 25 นาที

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

ในทางกลับกัน สําหรับ CVRP การเปลี่ยนแปลงของภาระงานแบบรวมจาก i เป็น j จะเท่ากับอุปสงค์ที่ i เสมอ จึงไม่มีความไม่เสถียร สําหรับปัญหาเช่นนี้ คุณสามารถตั้งค่า slack_max เป็น 0

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

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

สมมติว่ารถเลื่อนจากตําแหน่ง i ไปยังตําแหน่ง j ในขั้นตอนเดียว การล่าช้าเกี่ยวข้องกับตัวแปรต่อไปนี้ 

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

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