Dimensi

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

Bagian ini menjelaskan cara menentukan dan menggunakan dimensi.

Contoh dimensi

Berikut adalah beberapa contoh dimensi dari bagian sebelumnya.

  • Contoh VRPTW membuat dimensi untuk melacak waktu perjalanan kumulatif setiap kendaraan. Pemecah masalah menggunakan dimensi untuk menerapkan batasan sehingga kendaraan hanya dapat mengunjungi lokasi dalam jangka waktu lokasi.

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

Contoh di bawah menentukan dimensi untuk VRPTW menggunakan metode 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. Indeks yang merupakan referensi internal pemecah masalah untuk callback dibuat dengan metode seperti RegisterTransitCallback atau RegisterUnitaryTransitCallback.
  • slack_max: Maksimum untuk slack, variabel yang digunakan untuk mewakili waktu tunggu di lokasi. Lihat variabel slack di bawah untuk mengetahui detailnya. Jika masalah tidak memerlukan waktu tunggu, Anda biasanya dapat menetapkan slack_max ke 0.
  • capacity: Maksimum untuk jumlah total yang terakumulasi di sepanjang setiap rute. Gunakan capacity untuk membuat batasan seperti yang ada di CVRP. Jika masalah tidak memiliki batasan tersebut, Anda dapat menetapkan capacity ke nilai yang cukup besar untuk tidak menerapkan pembatasan pada rute — misalnya, jumlah semua entri matriks atau array yang digunakan untuk menentukan callback.
  • fix_start_cumulative_to_zero: Nilai boolean. Jika true (benar), nilai kumulatif kuantitas dimulai dari 0. Pada umumnya, nilai ini harus ditetapkan ke True. Namun, untuk VRPTW atau masalah dengan batasan resource, beberapa kendaraan mungkin harus dimulai setelah waktu 0 karena batasan periode waktu, sehingga Anda harus menyetel fix_start_cumulative_to_zero ke False untuk masalah ini.
  • dimension_name: String untuk nama dimensi, seperti 'Distance', yang dapat Anda gunakan untuk mengakses variabel lain dalam program.

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

Lihat halaman referensi RoutingModel untuk mengetahui metode lain yang membuat dimensi.

Bagian Simpan jendela waktu solusi ke daftar atau array menampilkan fungsi yang menyimpan data kumulatif dalam dimensi dalam daftar atau array.

Variabel Slack

Berikut adalah contoh yang mengilustrasikan variabel slack untuk masalah yang melibatkan waktu perjalanan. Misalkan kendaraan berpindah 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 tiba, atau waktu kumulatifnya di lokasi j adalah 175. Sebaliknya, kendaraan harus menunggu selama 25 menit di lokasi i sebelum berangkat; dengan kata lain, slack di lokasi i adalah 25.

Anda harus mengizinkan slack di VRPTW karena kendaraan mungkin harus menunggu sebelum mengunjungi lokasi karena adanya batasan jendela waktu. Dalam masalah seperti ini, tetapkan slack_max ke jumlah waktu maksimum yang Anda inginkan untuk mengizinkan kendaraan menunggu di lokasi sebelum melanjutkan ke lokasi berikutnya. Jika tidak masalah berapa lama waktu tunggu, cukup tetapkan slack_max ke angka yang sangat besar.

Di sisi lain, untuk CVRP, perubahan dalam 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 slack. Secara internal, dimensi menyimpan dua jenis variabel yang terkait dengan jumlah yang terakumulasi di sepanjang rute:

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

Dengan asumsi bahwa kendaraan pergi dari lokasi i ke lokasi j dalam satu langkah, slack ini terkait dengan variabel berikut: 

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

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