## RESEARCH ARTICLE • OPEN ACCESS
Optimalitas Rute pada Pengiriman Multiperjalanan dengan Armada Kendaraan Listrik Heterogen

## Kamilia Salsabilla, Toni Bakhtiar, dan Farida Hanum

## Volume 6, Issue 1, Pages 85–91, February 2024
Submit 7 Januari 2024, Direvisi 3 Februari 2024, Disetujui 5 Februari 2024 To Cite this Article : K. Salsabilla, T. Bakhtiar, dan F. Hanum,“Optimalitas Rute pada Pengi- riman Multiperjalanan dengan Armada Kendaraan Listrik Heterogen”, Jambura J. Math , vol. 6, no. 1, pp. 85–91, 2024, https://doi.org/10.37905/jjom.v6i1.23993
© 2024 by author(s)

## JOURNAL INFO • JAMBURA JOURNAL OF MATHEMATICS
u Homepage : http://ejurnal.ung.ac.id/index.php/jjom/index Ǽ Journal Abbreviation : Jambura J. Math. Х Frequency : Biannual (February and August) Ŷ Publication Language : English (preferable), Indonesia  DOI : https://doi.org/10.37905/jjom ʢ Online ISSN : 2656-1344 ǽ Editor-in-Chief : Hasan S. Panigoro Ÿ Publisher : Department of Mathematics, Universitas Negeri Gorontalo ƒ Country : Indonesia ̰ OAI Address : http://ejurnal.ung.ac.id/index.php/jjom/oai  Google Scholar ID : iWLjgaUAAAAJ Ͳ Email : info.jjom@ung.ac.id

## JAMBURA JOURNAL • FIND OUR OTHER JOURNALS
Jambura Journal of
Biomathematics Jambura Journal of Mathematics Education Jambura Journal of Probability and Statistics EULER : Jurnal Ilmiah Matematika, Sains, dan Teknologi
Optimalitas Rute pada Pengiriman Multiperjalanan dengan Armada Kendaraan Listrik Heterogen
Kamilia Salsabilla 1 , Toni Bakhtiar 1 , ∗  , dan Farida Hanum 1 
1 Divisi Riset Operasi, Departemen Matematika, IPB University, Indonesia
ABSTRAK. Kendaraan listrik menjadi tren utama dalam mobilitas berkelanjutan, mengurangi emisi dan ketergan- tungan pada bahan bakar fosil. Tantangan pemodelan optimasi rute terletak pada batasan daya jelajah baterai, waktu pengisian, dan keragaman jenis kendaraan listrik. Artikel ini mengeksplorasi optimalitas rute dalam sistem distribusi barang multiperjalanan menggunakan armada kendaraan listrik heterogen. Masalah perutean kendaraan listrik diformulasikan dalam bentuk pemrograman linear bilangan bulat campuran dengan tujuan mencari rute opti- mum berbiaya operasional terkecil. Fitur utama model ialah diperbolehkannya armada kendaraan listrik melakukan perjalanan tambahan untuk menyelesaikan tugas distribusi. Model diimplementasikan dalam dua contoh ilustratif sederhana, yaitu masalah pengiriman barang menggunakan armada kendaraan listrik homogen dan heterogen ber- dasarkan kapasitas muat dan kapasitas baterai. Setiap kasus memiliki 1 depot, 8 dan 10 pelanggan, serta 2 stasiun penggantian baterai, dan diselesaikan menggunakan metode branch-and-bound melalui Lingo 18.0. Hasil simulasi menunjukkan bahwa kapasitas baterai dan keberadaan stasiun penggantian baterai sangat menentukan rute yang terpilih.
ABSTRACT. Electric vehicles are emerging as a key trend in sustainable mobility, mitigating emissions, and reducing dependence on fossil fuels. The challenge in optimizing route modeling lies in some limitations such as battery range, charging time, and the diversity of electric vehicle types. This article explores the optimality of routes in a multiple trips distribution system using a heterogeneous fleet of electric vehicles. The electric vehicle routing problem is formulated as a mixed-integer linear programming aiming to find the most cost-efficient optimal route. A notable feature of the model allows electric vehicle fleets to undertake additional travel to complete distribution tasks, i.e., multiple trips. The model is implemented in two illustrative examples, involving the delivery of goods using homogeneous and heterogeneous electric vehicle fleets characterized by loading and battery capacities. Each case includes one depot, 8 and 10 customers, and 2 battery swapping stations, solved using the branch-and-bound method through Lingo 18.0. Simulation results indicate that battery capacity and the presence of battery swapping stations significantly influence the routes selection.
This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution-NonComercial 4.0 International License. Editorial of JJBM: Department of Mathematics, Uni- versitas Negeri Gorontalo, Jln. Prof. Dr. Ing. B. J. Habibie, Bone Bolango 96554, Indonesia.

## 1. Pendahuluan
Vehicle Routing Problem (VRP) merupakan topik penting dan menarik dalam optimisasi dan logistik. Masalah ini mendapat perhatian besar karena relevansinya dalam efisiensi operasional dan penghematan biaya transportasi bagi perusahaan logistik. VRP merupakan masalah optimisasi NP-hard yang bertujuan untuk menentukan rangkaian rute pengiriman dengan biaya terendah dari sebuah depot ke sekelompok pelanggan yang tersebar seca- ra geografis, dengan mempertimbangkan kendala-kendala tam- bahan [1] . Masalah ini pertama kali didefinisikan oleh Dantzig dan Ramser [2] sebagai Truck Dispatching Problem dan kemudi- an dikenal sebagai generalisasi Traveling Salesman Problem (TSP), yang bertujuan untuk mencari satu rute dengan biaya minimum untuk mengunjungi semua pelanggan.
Electric Vehicle Routing Problem (EVRP), di sisi lain, merupa-
∗ Penulis Korespondensi.
Check for updates
Research Article

## ARTICLE HISTORY
Submit 7 Januari 2024
Direvisi 3 Februari 2024 Disetujui 5 Februari 2024

## KATA KUNCI
Kendaraan Listrik
Masalah Rute Kendaraan
Multiperjalanan Rute Optimum

## KEYWORDS
Electric Vehicles Vehicle Routing Problems Multiple Trips Optimal Route
kan variasi VRP yang mempromosikan penggunaan kendaraan lis- trik ( electric vehicle ) dalam proses distribusi. Kehadiran kendara- an listrik menimbulkan tantangan baru dalam perencanaan rute karena perlunya dipertimbangkan aspek teknis seperti keterba- tasan jarak tempuh akibat keterbatasan kapasitas baterai dan ke- tersediaan infrastruktur stasiun pengisian daya kendaraan listrik umum (SPKLU). Karena kapasitas baterai yang terbatas, jangkau- an maksimum yang dapat dicapai kendaraan listrik dengan bate- rai yang terisi penuh ialah 160–240 km, jauh lebih rendah diban- dingkan jangkauan kendaraan konvensional 480–650 km [3–5] . Untuk mencapai jarak berkendara yang serupa dengan kendara- an konvensional, kendaraan listrik perlu mengunjungi SPKLU un- tuk mengisi daya ulang. Beberapa aspek teknis tentang baterai kendaraan listrik, seperti kurangnya kompatibilitas pengisi daya, perlunya manajemen energi yang sistematis, kurangnya prosedur yang dapat meminimumkan keputusan perutean dan penjadwal- an kendaraan listrik, penggunaan pendingin atau pemanas, re-
Email : tbakhtiar@apps.ipb.ac.id (T. Bakhtiar) Homepage : http://ejurnal.ung.ac.id/index.php/jjom/index / E-ISSN : 2656-1344 © 2024 by the Author(s).
gulasi pemerintah, dan langkah-langkah penggunaan kendaraan listrik dalam layanan transportasi, telah dibahas oleh Margaritis et al . [6] . Meski masih memiliki keterbatasan, EVRP memiliki po- tensi dan urgensi yang signifikan dalam bidang green logistics , ya- itu suatu konsep yang bertujuan untuk mengurangi dampak ne- gatif lingkungan dari kegiatan logistik, seperti emisi gas rumah kaca, polusi udara, dan penggunaan bahan bakar fosil. Tinjauan mengenai tantangan lingkungan, strategi, dan operasional inte- grasi kendaraan listrik dalam aktivitas logistik dan transportasi dilakukan oleh Juan et al . [7] . Survei tentang hasil-hasil pene- litian yang berkaitan dengan green vehicle routing problem (GVRP) diberikan oleh Macrina et al . [8] .
EVRP menjadi semakin penting karena pertumbuhan eks- ponensial kendaraan listrik di sektor transportasi akhir-akhir ini secara global [9] maupun di Indonesia [10] . Efisiensi operasio- nal, pengurangan emisi karbon, dan peningkatan keberlanjutan merupakan argumen utama untuk meneliti EVRP lebih progre- sif. Di beberapa negara, karena kebijakan dan peraturan baru terkait emisi gas rumah kaca di sektor transportasi, perusaha- an logistik dihadapkan pada pembayaran denda yang lebih tinggi untuk setiap gram emisi CO2/km [11] . Dengan penetrasi pasar kendaraan listrik yang semakin tinggi, banyak perusahaan yang mempertimbangkan integrasi kendaraan listrik ke dalam arma- da transportasi mengingat kendaraan listrik tidak menghasilkan emisi gas rumah kaca, menghasilkan sedikit kebisingan, dan tidak bergantung pada fluktuasi harga minyak. Li et al . [12] membahas masalah manajemen armada bus campuran yang terdiri atas bus dengan sumber daya listrik, diesel, gas alam terkompresi, dan di- esel hibrida, di mana dimaksimumkan manfaat total penggantian kendaraan lama dengan yang baru di bawah kendala anggaran di- sertai pengoptimuman penetapan rute untuk setiap bus selama periode perencanaan. Sementara itu, Lu et al . [13] memodelkan penjadwalan armada taksi yang terdiri atas kendaraan listrik dan konvensional.
VRP telah digunakan untuk memodelkan masalah pencari- an rute optimum distribusi barang dan telah memunculkan ba- nyak varian model, seperti VRP dengan kapasitas muatan kenda- raan terbatas ( capacitated VRP , CVRP), VRP dengan jendela waktu pelanggan ( VRP with time-window , VRPTW), VRP dengan banyak depot ( multidepot VRP , MDVRP), VRP dengan penjemputan dan pe- ngiriman ( VRP with pickup and delivery , VRPPD), VRP dengan pengi- riman terpisah ( VRP with split delivery , VRPSD), VRP dengan arma- da heterogen ( mixed fleet VRP , MFVRP), dan sebagainya [14, 15] . Selain metode eksak yang sifatnya terbatas hanya pada CVRP de- ngan 360 simpul [16] dan VRPTW dengan 50–100 simpul [17] , banyak prosedur heuristik, metaheuristik, dan hibrid diusulkan untuk memecahkan masalah VRP dan berbagai variannya. Pada kasus EVRP, ulasan komprehensif tentang model dan varian yang telah dikembangkan dapat dilihat pada [18–20] .
Ketika sebuah perusahaan distribusi menghadapi situasi di mana total permintaan pelanggan melebihi total kapasitas muat- an armada kendaraan yang dimiliki, maka salah satu penyelesaian yang dapat dilakukan ialah dengan mengizinkan satu atau lebih kendaraan melakukan perjalanan (ritasi) tambahan untuk menye- lesaikan pengiriman. Masalah ini dikenal sebagai VRP multiperja- lanan ( VRP with multiple trips , VRPMT) dan menjadi penting karena memiliki aplikasi yang luas dalam manajemen rantai pasok, misal- nya last-mile delivery [21] . Dengan memecahkan VRP multiperja-
lanan secara efisien, perusahaan dapat mengoptimumkan peng- gunaan armada kendaraan sehingga mengurangi biaya operasio- nal. Keharusan melakukan multiperjalanan dapat muncul bersa- ma dengan kondisi lain, seperti time window [22–24] , multiproduk dan kompartemen [25] , dan pengiriman terpisah [26] . Pembahas- an masalah distribusi multiperjalanan menggunakan kendaraan listrik (EVRPMT) masih jarang ditemukan. Zhang & Zhang [27] menerapkan model EVRPMT pada masalah evakuasi mengguna- kan bus listrik, Haryanto [28] membahas pemodelan last-mile deli- very PT Pos Indonesia dalam bentuk EVRPMT dan penyelesaiannya menggunakan algoritme variable neighborhood descent , sedangkan Wang et al . [29] mengimplementasikan algoritme hybrid variable neighborhood untuk menyelesaikan EVRPMT. Selain penggunaan kendaraan tunggal, implementasi algoritme heuristik tentu saja hanya menghasilkan solusi yang bersifat suboptimum.
Artikel ini membahas masalah pencarian rute optimum ar- mada kendaraan listrik multiperjalanan dengan kapasitas muatan dan kapasitas baterai berbeda ( heterogeneous fleet EVRPMT). Masa- lah dimodelkan dalam bentuk pemrograman linear bilangan bulat campuran ( mixed integer linear programming , MILP) dan diselesai- kan menggunakan metode eksak branch-and-bound sehingga di- peroleh solusi optimum global. Secara khusus, dalam artikel ini dianalisis pengaruh kapasitas muatan dan kapasitas baterai ser- ta kehadiran BSS terhadap pemilihan rute terbaik menggunakan armada kendaraan listrik homogen dan heterogen.

## 2. Model Distribusi Multiperjalanan
Bab ini membahas formulasi model EVRPMT dengan arma- da heterogen dalam bentuk MILP. Model Lin et al . [30] direlaksa- si dengan membolehkan digunakannya lebih dari satu kendaraan listrik dan setiap kendaraan dapat melakukan lebih dari satu rita- si. Pembahasan diawali dengan penyampaian asumsi dan penge- nalan notasi yang digunakan dalam membangun model.

## 2.1. Asumsi dan Notasi
Berikut adalah asumsi-asumsi yang realistis dan relevan di- gunakan dalam pemodelan EVRP multiperjalanan:
1. Perusahaan memiliki satu depot dan sejumlah kendaraan lis- trik.
2. Rute bersifat tertutup: di setiap ritasi, kendaraan listrik me- mulai dan mengakhiri rute di depot.
3. Kendaraan listrik yang digunakan berjenis battery electric ve- hicle (BEV) yang ditenagai secara eksklusif dari baterai yang dipasang di dalam kendaraan.
4. Setiap kendaraan dapat memiliki kapasitas muatan dan ka- pasitas baterai berbeda dan terbatas. BEV harus mengisi da- ya ulang ( recharging ) ketika diperlukan.
5. Pengisian daya listrik ulang dilakukan pada SPKLU berjenis battery swapping station (BSS).
6. Konsumsi daya kendaraan listrik hanya dipengaruhi oleh ja- rak yang ditempuh dan tidak dipengaruhi oleh kecepatan atau berat kendaraan. Laju konsumsi daya per satuan jarak bersifat konstan.
7. Baterai dengan berbagai kapasitas yang terisi penuh selalu tersedia di BSS dan depot. Setiap kendaraan meninggalkan depot dan BSS dengan baterai terisi penuh.
8. Permintaan barang oleh pelanggan diketahui dan bersifat te- tap.
Diagram ilustratif model EVRP multiperjalanan yang men- jadi fokus dalam artikel ini diberikan pada Gambar 1 .
Gambar 1. Model VRP multiperjalanan dengan armada ken- daraan listrik
Untuk memfasilitasi formulasi dan analisis model, diperke- nalkan beberapa himpunan, indeks, parameter, dan variabel beri- kut: N = { 1 , 2 , . . . , n } , K = { 1 , 2 , . . . , m } , B = { 1 , 2 , . . . , q } , dan R = { 1 , 2 , . . . , p } berturut-turut adalah himpunan semua pelanggan, himpunan semua kendaraan listrik, himpunan semua BSS, dan himpunan ritasi. Indeks i atau j digunakan untuk me- nunjuk pelanggan tertentu, indeks k untuk menunjuk kendara- an, dan indeks r untuk menunjuk ritasi. Indeks i = 0 dan i = n + 1 , dengan n adalah banyaknya pelanggan, berturut- turut menunjuk depot awal dan depot akhir yang terletak di lokasi yang sama. Didefinisikan juga beberapa gabungan him- punan berikut: A 1 himpunan semua pelanggan, BSS, dan de- pot awal ( A 1 = N ∪ B ∪ 0 ) , A n +1 himpunan semua pelangg- an, BSS, dan depot akhir ( A n +1 = N ∪ B ∪ n + 1 ) , dan A 1 ,n +1 himpunan semua pelanggan, BSS, depot awal, dan depot akhir ( A 1 ,n +1 = N ∪ B ∪ 0 , n + 1 ) . Semua parameter yang terlibat di- rangkum dalam Tabel 1 .
Tabel 1. Parameter model
Parameter Deskripsi Satuan n Banyaknya pelanggan orang m Banyaknya kendaraan listrik yang unit tersedia q Banyaknya BSS yang tersedia buah p Banyaknya ritasi kendaraan kali d ij Jarak pelanggan i ke pelanggan j kilometer δ i Banyaknya permintaan barang unit pelanggan i Q k
Kapasitas muatan kendaraan listrik k kilogram B k
Kapasitas baterai kendaraan listrik k kilowatt c k Biaya perjalanan kendaraan listrik k Rp/km β k Biaya penggantian baterai kendaraan Rp listrik k h k Laju konsumsi baterai kendaraan kw/km listrik k
Untuk mencatat aktivitas pada proses distribusi, didefinisi- kan variabel keputusan biner pada persamaan (1) :
x ijkr =     
  1 ; jika terdapat perjalanan dari i ke j menggunakan kendaraan k pada ritasi r 0 ; jika selainnya .
(1)
Selain variabel keputusan pada persamaan (1) , terdapat dua va- riabel lain yang terlibat dalam model yang akan diperkenalkan kemudian.

## 2.2. Model EVRPMT
Pada model EVRPMT, rute optimum dicari sedemikian se- hingga meminimumkan total biaya operasional kendaraan listrik z yang terdiri atas biaya perjalanan z 1 dan biaya penggantian ba- terai z 2 . Fungsi objektif ditulis pada persamaan (2) :
min z := z 1 + z 2 , (2)
dengan
z 1 = ∑ i ∈ A 1 ,n +1 ∑ j ∈ A 1 ,n +1 ∑ k ∈ K ∑ r ∈ R c k d ij x ijkr , (3)
z 2 = ∑ i ∈ B ∑ j ∈ A 1 ,n +1 \ B ∑ k ∈ K ∑ r ∈ R β k x ijkr . (4)
Dari persamaan (3) dapat dilihat bahwa biaya perjalanan bergantung pada jarak yang ditempuh dengan biaya satuan yang berbeda menurut kendaraan, sedangkan dari persamaan (4) , di- ketahui bahwa biaya penggantian baterai bergantung pada ken- daraan listrik yang digunakan.
Kendala-kendala yang terlibat dalam model EVRPMT me- liputi batasan-batasan standar yang biasa ditemui dalam model VRP, kondisi yang membolehkan kendaraan melakukan perjala- nan atau ritasi tambahan, dan syarat-syarat yang harus dipenuhi oleh kendaraan listrik, yaitu:
1. Setiap pelanggan dikunjungi tepat satu kali oleh satu ken- daraan listrik:
∑ j ∈ N ,i ̸ = j ∑ k ∈ K ∑ r ∈ R x ijkr = 1 , ∀ i ∈ A 1 , (5)
∑ i ∈ N ,i ̸ = j ∑ k ∈ K ∑ r ∈ R x ijkr = 1 , ∀ j ∈ A n +1 . (6)
Kendala pada persamaan (5) memastikan bahwa pada ritasi r , pelanggan i dikunjungi satu kali oleh kendaraan k sebe- lum melanjutkan ke pelanggan berikutnya atau ke BSS. Ken- dala pada persamaan (6) menjamin bahwa pelanggan j atau BSS atau depot (akhir) dikunjungi satu kali setelah kendara- an mengunjungi pelanggan i .
2. Kendaraan listrik boleh mengunjungi BSS beberapa kali jika diperlukan:
∑ i ∈ A 1 ,i ̸ = j x ijkr ≥ 0 , ∀ j ∈ B , ∀ k ∈ K , ∀ r ∈ R , (7) ∑ j ∈ A n +1 ,i ̸ = j x ijkr ≥ 0 , ∀ i ∈ B , ∀ k ∈ K , ∀ r ∈ R . (8)
Kendala (7) dan (8) berturut-turut menyatakan perjalanan menuju dan meninggalkan BSS.
3. Di setiap ritasi, setiap kendaraan listrik mengawali perjala- nan dari depot dan kembali ke depot ketika perjalanan telah selesai:
∑ j ∈ A n +1 x 0 jkr ≥ 0 , ∀ k ∈ K , ∀ r ∈ R , (9) ∑ i ∈ A 1 x i,n +1 ,kr ≥ 0 , ∀ k ∈ K , ∀ r ∈ R . (10)
Dua kendala (9) dan (10) , memastikan terjadinya rute tertu- tup ( closed route ).
4. Kendala pada persamaan (11) menjamin rute yang dilalui kendaraan membentuk rangkaian simpul yang terhubung tanpa ada jeda atau segmen yang terputus:

## ∑
i ∈ A 1 x ilkr = ∑ j ∈ A n +1 x ljkr , ∀ l ∈ N ∪ B , ∀ k ∈ K , ∀ r ∈ R . (11)
Kendala kontinuitas rute di atas merupakan kendala pen- ting dalam model VRP untuk memastikan bahwa kendaraan mengunjungi pelanggan dengan cara yang logis dan berurut- an. Kendala ini merupakan sifat konservasi aliran, yaitu jum- lah kunjungan masuk sama dengan jumlah kunjungan keluar di setiap simpul.
5. Pada suatu ritasi, setiap kendaraan tidak boleh mengunjungi kembali pelanggan atau BSS yang sama:
x iikr = 0 , ∀ i ∈ A 1 ,n +1 , ∀ k ∈ K , ∀ r ∈ R . (12)
6. Di setiap ritasi, banyaknya barang yang dibawa oleh suatu kendaraan tidak melebihi kapasitas muatan kendaraan ter- sebut:
∑ i ∈ A 1 ,n +1 ∑ j ∈ A 1 ,n +1 ,i ̸ = j δ i x ijkr ≤ Q k , ∀ k ∈ K , ∀ r ∈ R . (13)
Kendala (13) sekaligus menjamin bahwa permintaan barang setiap pelanggan terpenuhi.
7. Baterai terisi penuh setiap kendaraan meninggalkan depot atau BSS:
y 1 kr = B k , ∀ k ∈ K , ∀ r ∈ R , (14) y ikr = B k , ∀ i ∈ B , ∀ k ∈ K , ∀ r ∈ R . (15)
Pada kendala (14) dan (15) , y ikr didefinisikan sebagai da- ya yang tersisa pada baterai kendaraan k saat mengunjungi simpul i pada ritasi r dan merupakan variabel yang harus di- tentukan oleh model. Variabel ini harus memenuhi kendala berikutnya.
8. Daya yang tersisa pada baterai kendaraan k saat mengunju- ngi simpul i pada ritasi r bersifat taknegatif dan tidak mung- kin melebihi kapasitas baterai:
0 ≤ y ikr ≤ B k , ∀ i ∈ A 1 ,n +1 , ∀ k ∈ K , ∀ r ∈ R . (16)
9. Daya yang tersisa pada baterai kendaraan saat mengunju- ngi suatu simpul bergantung pada jarak yang ditempuh dari simpul sebelumnya:
0 ≤ y jkr ≤ y ikr − h k d ij x ijkr + B k (1 − x ijkr ) , ∀ i ∈ N ∪ 0 , ∀ j ∈ A n +1 , i ̸ = j, ∀ k ∈ K , ∀ r ∈ R , (17)
0 ≤ y jkr ≤ B k − h k d lj x ljkr , ∀ l ∈ B , ∀ j ∈ A n +1 , i ̸ = j, ∀ k ∈ K , ∀ r ∈ R . (18)
Jika terjadi perjalanan dari pelanggan i ke pelanggan j , yaitu x ijkr = 1 , maka kendala (17) berubah menjadi 0 ≤ y jkr ≤ y ikr − h k d ij , yang menunjukkan pengurangan daya listrik akibat perjalanan tersebut. Jika tidak terjadi, yaitu x ijkr = 0 , maka kendala tersebut menjadi 0 ≤ y jkr ≤ y ikr + B k yang selalu terpenuhi. Situasi serupa ditunjukkan kendala (18) ketika kendaraan baru saja meninggalkan BSS. 10. Subtur ( subtour ) mengacu pada gelung ( loops ) atau sirkuit ( cir- cuits ) yang lebih kecil yang terbentuk dalam rute yang lebih besar. Jika dibiarkan, subtur ini dapat menghasilkan solusi yang suboptimal di mana kendaraan akhirnya menciptakan rute yang tidak efisien atau takfisibel [14] . Kendala eliminasi subtur membantu mencegah terjadinya situasi ini:
u ikr − u jkr + nx ijkr ≤ n − 1 ,
∀ i ∈ A 1 , ∀ j ∈ A 1 ,n +1 , i ̸ = j,
∀ k ∈ K , ∀ r ∈ R . (19)
dengan u ikr merupakan variabel yang merepresentasikan peringkat simpul i pada rute akhir. Variabel ini ditentukan secara optimal oleh model. Kendala eliminasi subtur (19) mengikuti formulasi Miller-Tucker-Zemlin (MTZ) [31] . 11. Kendala biner dan kendala ketaknegatifan:
x ijkr ∈ { 0 , 1 } , ∀ i, j ∈ A 1 ,n +1 , ∀ k ∈ K , ∀ r ∈ R , (20)
u ikr ≥ 0 , ∀ i ∈ A 1 ,n +1 , ∀ k ∈ K , ∀ r ∈ R . (21)

## 3. Hasil dan Pembahasan
Model EVRPMT yang menjadi fokus pembahasan dalam ar- tikel ini dapat dinyatakan sebagai meminimumkan biaya opera- sional (2) terhadap kendala-kendala (5) – (21) . Pada bab ini, diba- has penerapan model pada masalah distribusi barang multiperja- lanan. Dua contoh ilustratif ditinjau, yaitu model EVRPMT meng- gunakan armada kendaraan listrik heterogen dan homogen, un- tuk memvalidasi keandalan model.

## 3.1. Contoh Ilustratif
Terdapat dua kasus yang ditinjau dalam implementasi mo- del EVRPMT dan dibedakan menurut banyaknya pelanggan, ser- ta kapasitas muatan dan kapasitas baterai seperti disarikan pa- da Tabel 2 . Contoh 1 mengoperasikan armada kendaraan listrik heterogen sedangkan Contoh 2 homogen. Contoh 1 melibatk- an 8 pelanggan, Contoh 2 menggunakan 10 pelanggan, dan pada keduanya terdapat 1 Depot dan 2 BSS. Jarak antarsimpul (depot,
Tabel 2. Studi kasus implementasi model EVRPMT
Armada Jumlah Pelanggan Jumlah Kendaraan Kapasitas Muatan Kapasitas Baterai Heterogen (Contoh 1) 8 2 220 130 150 100 Homogen (Contoh 2) 10 2 200 130 200 130
Tabel 3. Jarak antarsimpul dan tingkat permintaan barang Contoh 1 d ij D P1 P2 P3 P4 P5 P6 P7 P8 BSS1 BSS2 δ i
D 0 42 60 22 47 44 20 56 47 56 40 0 P1 0 21 25 75 60 52 74 56 30 65 90
P2 0 63 110 116 38 29 41 75 25 105
P3
0 35 54 26 62 39 105 26 55 P4 0 62 35 33 62 25 55 85 P5
0 29 44 21 46 47 85 P6
0 24 37 19 32 70 P7
0 27 38 21 50
P8
0 25 41 94 BSS1 0 39 0 BSS2 0 0 Tabel 4. Jarak antarsimpul dan tingkat permintaan barang Contoh 2
d ij D P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 BSS1 BSS2 δ i
D 0 42 60 22 47 44 20 56 47 39 31 56 40 0 P1 0 21 25 75 60 52 74 56 67 60 30 65 90 P2 0 63 110 116 38 29 41 22 116 75 25 85 P3 0 35 54 26 62 39 53 54 105 26 55 P4 0 62 35 33 62 28 62 25 55 115 P5 0 29 44 21 45 33 46 47 55 P6 0 24 37 89 36 19 32 80 P7 0 27 47 73 38 21 50
P8 0 42 40 25 41 64 P9 0 43 35 20 75 P10 0 46 47 60 BSS1 0 39 0 BSS2 0 0
pelanggan, BSS) yang diasumsikan simetrik dan tingkat perminta- an barang ( δ i ) merupakan data hipotetik dan diberikan pada Ta- bel 3 dan Tabel 4 . Depot dilambangkan dengan D sedangkan pe- langgan dengan P1, P2, dan seterusnya.
Pada Contoh 1, biaya perjalanan ialah 2000 rupiah/km un- tuk kendaraan pertama dan 1500 rupiah/km untuk kendaraan ke- dua, sedangkan biaya penggantian baterai berturut-turut ialah 1000 rupiah dan 900 rupiah setiap kali ganti. Pada Contoh 2 de- ngan kendaraan listrik homogen, biaya perjalanan ialah 2000 ru- piah/km dan biaya ganti baterai 1000 rupiah untuk setiap kenda- raan. Diasumsikan bahwa untuk menempuh jarak 1 km diperlu- kan daya baterai sebesar 1 kw.
Banyaknya ritasi p dapat ditentukan dengan membanding- kan total permintaan barang oleh pelanggan dan total kapasitas muatan. Pada Contoh 1, total kapasitas muatan ialah 220+150 = 370 kg dan total permintaan barang 634 kg, sehingga diperluk- an 2 ritasi. Pada Contoh 2, total kapasitas muatan ialah 400 kg dan total permintaan barang 729 kg, sehingga dibutuhkan 2 ri- tasi juga. Rangkuman nilai-nilai parameter yang digunakan pada Contoh 1 dan Contoh 2 diberikan pada Tabel 5 .

## 3.2. Rute Optimum
Contoh 1 merupakan masalah EVRPMT dengan armada he- terogen karena dua kendaraan listrik yang digunakan memiliki kapasitas muatan dan kapasitas baterai berbeda. Implementasi model pada peranti lunak Lingo 18.0 menggunakan mesin stan- dar (RAM 8 GB) memberikan biaya operasional minimum sebesar z ∗ = 827900 rupiah (optimum global) yang dicapai dalam wak- tu 7 , 85 detik (setara dengan 58613 iterasi metode branch-and- bound ).
Pada Contoh 1, kedua kendaraan melakukan dua kali ritasi untuk menyelesaikan proses distribusi. Kendaraan pertama pa- da ritasi pertama memiliki rute D-P2-P1-D dengan jarak tempuh 60+21+42 = 123 km, sehingga masih di bawah kapasitas baterai sebesar 130 kw. Akibatnya, kendaraan pertama tidak perlu meng- ganti baterai pada ritasi pertama. Pada ritasi kedua, rute yang dilalui ialah D-P5-P8-D dengan jarak tempuh 44 + 21 + 47 = 112 km tanpa harus mengunjungi BSS. Sementara itu, kendaraan ke- dua dengan kapasitas baterai lebih kecil memulai rute dengan tidak biasa. Begitu meninggalkan depot D, kendaraan langsung menuju BSS1 yang berjarak 56 km untuk menukar baterai. De- ngan daya terisi penuh, kendaraan meninggalkan BSS1 menuju
Tabel 5. Nilai parameter model Parameter Deskripsi Contoh 1 Contoh 2 Satuan n Banyaknya pelanggan 8 10 orang m Banyaknya BEV 2 2 unit q Banyaknya BSS 2 2 buah p Banyaknya ritasi 2 2 kali d ij Jarak antarsimpul lihat Tabel 3 lihat Tabel 4 kilometer δ i Banyaknya permintaan
lihat Tabel 3 lihat Tabel 4 unit Q k Kapasitas muatan 220, 150 130, 100 kilogram B k Kapasitas baterai 130, 100 130, 130 kilowatt c k Biaya perjalanan 2000, 1500 2000, 2000 Rp/km β k Biaya ganti baterai 1000, 900 1000, 1000 Rp h k Laju konsumsi baterai 1 1 kw/km
P4, P3, dan kembali ke depot. Rute D-BSS1-P4-P3-D memiliki ja- rak tempuh 138 km. Pada saat kembali ke depot, daya baterai yang tersisa ialah 18 kw. Pada ritasi kedua, kendaraan melaku- kan distribusi barang melalui rute D-P6-P7-D dengan jarak tem- puh 100 km, sama persis dengan kapasitas baterai. Rincian rute beserta status daya baterai dan muatan Contoh 1 dapat dilihat pada Tabel 6 .
Tabel 6. Rute optimum Contoh 1 Kendaraan Ritasi Rute Daya Baterai (kw) Muatan (kg) 1 1 D 130 175 P2 70 85 P1 49 0 D 7 0 2 D 130 179 P5 86 94 P8 65 0 D 18 0 2 1 D
100 140 BSS1 100 140 P4 75 55 P3 40 0 D 18 0 2 D 100 120 P6 80 50 P7 56 0 D 0 0
Contoh 2 membutuhkan waktu komputasi lebih lama di- bandingkan Kasus 1, yaitu 163 , 1 detik. Metode branch-and-bound membutuhkan 845615 iterasi untuk mendapatkan solusi opti- mum 969000 rupiah (optimum global). Hal ini tentu saja wajar karena Contoh 2 memiliki jumlah pelanggan yang lebih besar.
Seperti dapat dilihat pada Tabel 7 , kendaraan pertama me- nempuh rute D-P10-P5-P6-D pada ritasi pertama dan rute D-P9- P4-D pada ritasi kedua dengan jarak tempuh berturut-turut 113 km dan 114 km. Karena jarak tempuh masih di dalam jangkauan baterai 130 kw, maka kendaraan pertama tidak perlu mengganti baterai di BSS. Sementara itu kendaraan kedua harus mengunju- ngi BSS2 sesaat sebelum kembali ke depot pada ritasi pertama (D-P8-P7-P2-BSS2-D). Tindakan ini perlu dilakukan karena ketika sampai di P2 daya baterai tersisa 27 kw sementara jarak P2 ke depot ialah 60 km. Pada ritasi kedua, kendaraan kedua melalui rute D-P3-P1-D tanpa singgah ke BSS.
Tabel 7. Rute optimum Contoh 2
Kendaraan Ritasi Rute Daya Baterai (kw) Muatan (kg) 1 1 D 130 195 P10 99 135 P5 66 80 P6 37 0 D 17 0 2 D 130 190 P9 91 115 P4 63 0 D 16 0
2 1 D 130 195 P8 83 135 P7 56 85 P2 27 0 BSS2 130 0 D 90 0 2 D 130 145 P3 108 90 P1 83 0 D 41 0

## 4. Kesimpulan
Pada artikel ini sudah diajukan model pencarian rute opti- mum masalah distribusi barang menggunakan kendaraan listrik. Fitur utama yang ditawarkan model ialah penggunaan armada kendaraan listrik dengan setiap kendaraan listrik dimungkinkan melakukan perjalanan tambahan ( multiple trips ) untuk menyelesai- kan proses distribusi. Fitur lain yang juga dimiliki oleh model ialah penggunaan armada kendaraan listrik dengan karakteristik yang berbeda, meliputi kapasitas muatan, kapasitas baterai, dan laju konsumsi baterai. Model EVRPMT sudah diimplementasikan pada dua contoh sederhana, yaitu armada homogen dan hetero- gen, yang keduanya melibatkan 1 depot, 2 BSS, dan 2 kendaraan listrik, serta 8 dan 10 pelanggan, berturut-turut. Kedua masalah perutean dapat diselesaikan dalam waktu relatif cepat (kurang dari tiga menit) menggunakan metode eksak branch-and-bound . Pada kasus armada heterogen, rute optimum ialah D-P2-P1-D dan D-P5-P8-D untuk BEV 1 serta D-BSS1-P4-P3-D dan D-P6-P7-D un- tuk BEV 2. Pada kasus armada homogen, rute optimum diberikan oleh D-P10-P5-P6-D dan D-P9-P4-D untuk BEV 1 serta D-P8-P7-P2- BSS2-D dan D-P3-P1-D untuk BEV 2. Terlihat bahwa keberagaman kapasitas baterai dan keberadaan BSS sangat mempengaruhi pe- nentuan rute optimum.
Model EVRPMT tentu saja dapat dikembangkan dengan me- nambahkan fitur baru, seperti adanya jendela waktu pelanggan ( time window ) dan/atau pengiriman terpisah ( split delivery ). Peng- gunaan kombinasi kendaraan konvensional dan kendaraan listrik ( hybrid ) juga merupakan topik penelitian yang menarik. Jika jum- lah simpul yang terlibat dalam distribusi cukup besar, maka perlu dirancang metode-metode penyelesaian berbasis heuristik atau metaheuristik yang lebih efisien dalam hal waktu proses.
Kontribusi Penulis. Kamilia Salsabilla: Konseptualisasi, pengumpulan data, metodologi, analisis formal, investigasi, penulisan draft, dan visu- alisasi. Toni Bakhtiar: Konseptualisasi, validasi, penulisan pembahas- an dan pengeditan, supervisi. Farida Hanum: Konseptualisasi, validasi, penulisan pembahasan dan pengeditan, supervisi. Semua penulis telah membaca dan menyetujui versi manuskrip yang diterbitkan.
Ucapan Terima Kasih. Para penulis menyampaikan terima kasih kepada editor dan reviewer atas pembacaan yang cermat, kritik yang mendalam, dan rekomendasi yang praktis untuk meningkatkan kualitas tulisan ini.
Pembiayaan. Penelitian ini tidak menerima pembiayaan eksternal.
Konflik Kepentingan. Para penulis menyatakan tidak ada konflik kepen- tingan yang terkait dengan artikel ini.

## Referensi
[1] G. Laporte, ”Fifty years of vehicle routing,” Transp. Sci. , vol. 43, no. 4, pp. 408–416, 2009, doi: 10.1287/trsc.1090.0301 .
[2] G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Manag. Sci. , vol. 6, no. 1, pp. 80–91, 1959, doi: 10.1287/mnsc.6.1.80 .
[3] K. Young, C. Wang, L. Y. Wang, and K. Strunz, “Electric vehicle battery te- chnologies,” in R. Garcia-Valle and J. Pecas-Lopes (eds), Electric Vehicle Inte- gration into Modern Power Networks. Power Electronics and Power Systems , New York, NY: Springer, 2013, doi: 10.1007/978-1-4614-0134-6_2 .
[4] J. van Duin, L. Tavasszy, and H. Quak, “Towards e(lectric)-urban freight: First promising steps in the electronic vehicle revolution,” Eur. Transp. Trasp. Eur. , no. 54, pp. 1–19, 2013.
[5] C. Liao, S. Lu, and Z. M. Shen, “The electric vehicle touring problem,” Transp. Res. B Methodol. , vol. 86, pp. 163–180, 2016, doi: 10.1016/j.trb.2016.02.002 .
[6] D. Margaritis, A. Anagnostopoulou, A. Tromaras, and M. Boile, “Ele- ctric commercial vehicles: practical perspectives and future research directions,” Res. Transp. Bus. Manag. , vol. 18, pp. 4–10, 2016, doi: 10.1016/j.rtbm.2016.01.005 .
[7] A. Juan, C. Mendez, J. Faulin, J. de Armas, and S. Grasman, “Electric vehicles in logistics and transportation: a survey on emerging environmental, stra- tegic, and operational challenges,” Energies , vol. 9, no. 2, pp. 86, 2016, doi: 10.3390/en9020086 .
[8] G. Macrina, L. D. P. Pugliese, and F. Guerriero, “The green-vehicle routing problem: a survey.” In H. Derbel, B. Jarboui, and P. Siarry (eds), Mode- ling and optimization in green logistics , pp. 1–26, 2020, Springer, Cham, doi: 10.1007/978-3-030-45308-4_1 .
[9] I. E. A., “Global EV outlook 2023: catching up with climate ambitions,” In- ternational Energy Agency, 2023.
[10] F. A. Padhilah, P. Aji, and I. R. F. Surya, “Indonesia Electric Vehicle Outlook (IEVO) 2023,” Institute for Essential Services Reform (IESR), 2023.
[11] P. Martin, “Weak emission standards and Australia’slow takeup of electric vehicles,” Econ. Papers , vol. 41, no. 4, pp. 390–395, 2022, doi: 10.1111/1759- 3441.12371 .
[12] L. Li, H. K. Lo, F. Xiao, and X. Cen, “Mixed bus fleet management strategy forminimizing overall and emissions external costs,” Transp. Res. D Transp. Environ. , vol. 60, pp. 104–118, 2018, doi: 10.1016/j.trd.2016.10.001 .
[13] C. C. Lu, S. Yan, and Y. W. Huang, “Optimal scheduling of a taxi fle- et with mixed electric and gasoline vehicles to service advance reserva- tions,” Transp. Res. C Emerg. Technol. , vol. 93, pp. 479–500, 2018, doi: 10.1016/j.trc.2018.06.015 .
[14] P. Toth and D. Vigo, The vehicle routing problem , Philadelphia, PA: Society for Industrial and Applied Mathematics, 2002, doi: 10.1137/1.9780898718515 .
[15] T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “Heuristics for multi- attribute vehicle routing problems: a survey and synthesis,” Eur. J. Oper. Res. , vol. 231, no. 1, pp. 1–21, 2013, doi: 10.1016/j.ejor.2013.02.053 .
[16] D. Pecin, A. Pessoa, M. Poggi, and E. Uchoa, “Improved branch-cut-and-price for capacitated vehicle routing,” Math. Prog. Comput. , vol. 9, no. 1, pp. 61– 100, 2017, doi: 10.1007/s12532-016-0108-8 .
[17] R. Baldacci, A. Mingozzi, and R. Roberti, “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints,” Eur. J. Oper. Res. , vol. 218, no. 1, pp. 1–6, 2012, doi: 10.1016/j.ejor.2011.07.037 .
[18] Y. Xiao, Y. Zhang, I. Kaku, R. Kang, and X. Pan, “Electric vehicle routing pro- blem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption,” Renew. Sust. Energ. Rev ., vol. 151, pp. 111567, 2021, doi: 10.1016/j.rser.2021.111567 .
[19] H. Qin, X. Su, T. Ren, and Z. Luo, “A review on the electric vehicle routing problems: variants and algorithms,” Front. Eng. Manag ., vol. 8, pp. 370–389, 2021, doi: 10.1007/s42524-021-0157-1 .
[20] Y. Huang, “A review on the electric vehicle routing problem and its va- riations,” Front. Soc. Sci. Technol ., vol. 5, no. 5, pp. 85–90, 2023, doi: 10.25236/FSST.2023.050514 .
[21] K. V. Tiwari and S. K. Sharma, “An optimization model for vehicle routing problem in last-mile delivery,” Expert Syst. Appl ., vol. 222, pp. 119789, 2023, doi: 10.1016/j.eswa.2023.119789 .
[22] N. Huang, J. Li, W. Zhu, and H. Qin, “The multi-trip vehicle routing problem with time windows and unloading queue at depot,” Transp. Res. E: Logist. Transp. Rev ., vol. 152, pp. 102370, 2021, doi: 10.1016/j.tre.2021.102370 .
[23] L. Zhen, C. Ma, K. Wang, L. Xiao, and W. Zhang, “Multi-depot multi- trip vehicle routing problem with time windows and release dates,” Transp. Res. E: Logist. Transp. Rev ., vol. 135, pp. 101866, 2020, doi: 10.1016/j.tre.2020.101866 .
[24] R. Xu, S. Li, and J. Wu, “Multi-trip vehicle routing problem with time windo- ws and resource synchronization on heterogeneous facilities,” Systems , vol. 11, no. 8, pp. 412, 2023, doi: 10.3390/systems11080412 .
[25] P. Kabcome and T. Mouktonglang, “Vehicle routing problem for multiple pro- duct types, compartments, and trips with soft time windows,” Int. J. Math. Math. Sci ., vol. 2015, article ID 126754, 2015, doi: 10.1155/2015/126754 .
[26] F. Hanum, M. R. N. Hadi, A. Aman, and T. Bakhtiar, “Vehicle routing problems in rice-for-the-poor distribution,” Decis. Sci. Lett. , vol. 8, no. 3, pp. 323–338, 2019, doi: 10.5267/j.dsl.2018.11.001 .
[27] J. Zhang and X. Zhang, “A multi-trip electric bus routing model considering equity during short-notice evacuations,” Transp. Res. D: Transp. Environ ., vol. 110, pp. 103397, 2022, doi: 10.1016/j.trd.2022.103397 .
[28] Z. I. Haryanto, “Multi trip electric vehicle routing problem backhaul with time window dalam pengadopsian kendaraan listrik pada jasa layanan last mile,” Institut Teknologi Sepuluh Nopember, 2023.
[29] W. Wang, D. Ding, and S. Cao, “Hybrid variable neighborhood search al- gorithm for the multi-trip and heterogeneous-fleet electric vehicle rou- ting problem, J. Syst. Simul., vol. 34, no. 4, pp. 910–919, 2022, doi: 10.16182/j.issn1004731x.joss.21-1133 .
[30] J. Lin, W. Zhou, and O. Wolfson, “Electric vehicle routing problem,” Transp. Res. Proc ., vol. 12, pp. 508–521, 2016, doi: 10.1016/j.trpro.2016.02.007 .
[31] C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formula- tion of traveling salesman problem, J. ACM , vol. 7, no. 4, pp. 326–329, 1960, doi: 10.1145/321043.321046 .