Dimensions

Pemecah masalah pemilihan rute menggunakan objek yang disebut dimensi untuk melacak kuantitas yang terakumulasi di sepanjang rute kendaraan, seperti waktu perjalanan atau, jika kendaraan melakukan pengambilan dan pengiriman, total berat yang dibawanya kami. Jika masalah {i>routing<i} melibatkan jumlah tersebut, baik dalam batasan fungsi tujuan, Anda perlu menentukan dimensi untuk menentukannya.

Bagian ini menjelaskan cara menetapkan dan menggunakan dimensi.

Contoh dimensi

Berikut adalah beberapa contoh dimensi dari bagian sebelumnya.

  • Contoh VRPTW membuat dimensi untuk dilacak kumulatif waktu tempuh untuk setiap kendaraan. Pemecah masalah menggunakan dimensi untuk menegakkan batasan di mana kendaraan hanya dapat mengunjungi lokasi dalam periode waktu.

  • Contoh CVRP membuat dimensi untuk permintaan (mis., bobot atau volume paket yang akan diambil), yang melacak beban kumulatif yang dibawa kendaraan di sepanjang rutenya. Pemecah masalah menggunakan dimensi untuk menerapkan batasan beban kendaraan tidak boleh melebihi kapasitasnya.

Contoh di bawah ini menentukan dimensi untuk VRPTW menggunakan 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)

Metode AddDimension memiliki input berikut:

  • callback_index: Indeks untuk callback yang menampilkan kuantitas. Tujuan , yang merupakan referensi internal pemecah masalah ke callback, dibuat oleh seperti RegisterTransitCallback atau RegisterUnitaryTransitCallback.
  • slack_max: Maksimum untuk slack, variabel yang digunakan untuk mewakili proses menunggu waktu di beberapa lokasi. Lihat variabel slack di bawah untuk spesifikasi pendukung. Jika masalahnya tidak terkait waktu tunggu, Anda biasanya dapat menyetel slack_max menjadi 0.
  • capacity: Maksimum untuk total jumlah yang terakumulasi di sepanjang setiap rute. Gunakan capacity untuk membuat batasan seperti yang ada di CVRP. Jika masalah Anda tidak memiliki Anda dapat menetapkan capacity ke nilai yang cukup besar untuk memberlakukan pembatasan pada rute-rute —misalnya, jumlah semua entri matriks atau array yang digunakan untuk menentukan callback.
  • fix_start_cumulative_to_zero: Nilai Boolean. Jika benar, nilai kumulatif dari jumlah tersebut dimulai dari 0. Biasanya, parameter ini harus disetel ke True. Namun, untuk VRPTW atau masalah dengan batasan sumber daya, beberapa kendaraan mungkin harus dimulai setelah waktu 0 karena batasan jangka waktu, jadi Anda harus tetapkan fix_start_cumulative_to_zero ke False untuk masalah ini.
  • dimension_name: String untuk nama dimensi, seperti 'Distance', yang dapat digunakan untuk mengakses variabel di tempat lain dalam program.

Program CVRP membuat jenis dimensi yang sedikit berbeda menggunakan AddDimensionWithVehicleCapacity . Metode ini memerlukan array kapasitas, dengan satu entri untuk setiap kendaraan. (Sebaliknya, AddDimension menggunakan satu nilai untuk capacity, jadi semua kendaraan dianggap memiliki kapasitas yang sama.)

Lihat RoutingModel halaman referensi untuk metode lain yang membuat dimensi.

Bagian ini Menyimpan periode waktu solusi ke daftar atau array menampilkan fungsi yang menyimpan data kumulatif dalam dimensi dalam daftar atau array.

Variabel Slack

Berikut adalah contoh yang menggambarkan variabel {i> slack <i}untuk masalah yang melibatkan waktu tempuh. Misalkan kendaraan bergerak dari lokasi i ke lokasi j dalam satu langkah rutenya, dan bahwa:

  • Waktu perjalanan kumulatif kendaraan di i adalah 100 menit.
  • Waktu perjalanan kumulatif kendaraan di j adalah 200 menit.
  • Waktu tempuh dari i ke j adalah 75 menit.

Kendaraan tidak dapat meninggalkan lokasi i segera setelah kedatangan, atau biaya kumulatifnya waktu di lokasi j adalah 175. Sebaliknya, kendaraan harus menunggu selama 25 menit di lokasi i sebelum keberangkatan; dengan kata lain, {i>slack <i}di lokasi i adalah 25.

Anda harus menghindari kelonggaran dalam VRPTW karena kendaraan mungkin harus menunggu sebelum yang mengunjungi suatu lokasi, karena kendala waktu. Pada masalah seperti ini, atur slack_max ke jumlah waktu maksimum yang Anda inginkan untuk mengantre kendaraan sebuah lokasi sebelum melanjutkan ke lokasi berikutnya. Jika tidak penting berapa lama mereka menunggu, cukup setel slack_max ke angka yang sangat besar.

Di sisi lain, untuk CVRP, perubahan akumulasi beban dari i menjadi j selalu sama dengan permintaan pada i, sehingga tidak ada slack. Untuk masalah seperti ini, Anda dapat menetapkan slack_max ke 0.

Selanjutnya, kita akan memberikan definisi formal tentang {i>slack<i}. Secara internal, dimensi menyimpan dua jenis variabel yang terkait dengan kuantitas yang terakumulasi sepanjang rute:

  • Variabel transportasi umum: Peningkatan atau penurunan jumlah di setiap langkah rute. Jika i -> j adalah satu langkah dalam rute, variabel transportasi umum adalah i, j entri matriks transit (untuk callback transit), atau cukup nilai callback di lokasi i (jika callback hanya bergantung pada satu lokasi).
  • Variabel kumulatif: Total jumlah akumulasi di setiap lokasi. Anda dapat mengakses variabel kumulatif di lokasi i dengan dimension_name.CumulVar(i). Misalnya, lihat batasan periode waktu dalam contoh VRPTW.

Dengan asumsi bahwa kendaraan berangkat dari lokasi i ke lokasi j dalam satu langkah, slack berkaitan dengan variabel-variabel ini sebagai berikut: 

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

Untuk detail selengkapnya tentang dimensi, lihat RoutingDimension di bagian referensi.