Dünya Şampiyonlarına Giden Yol: Cainiao'nun Araç Yolu Planlama Motorunun Ar-Ge Süreci
Alimei'nin Kılavuzu: Araç Yönlendirme Problemi (VRP), lojistik alanında büyük akademik araştırma önemi ve pratik uygulama değeri olan en klasik optimizasyon problemlerinden biridir. İki yıllık araştırma ve geliştirmeden sonra, Cainiao Ağları konusunda kıdemli bir algoritma uzmanı olan Hu Haoyuan, depo ve dağıtım akıllı algoritma ekibinin, Cainiao'nun birçok dahili ve harici işletmesi için teknik destek sağlayan eksiksiz ve güçlü bir araç yolu planlama ve çözme motorunu kademeli olarak geliştirmesine öncülük etti. Algoritmanın sürekli araştırılması ve cilalanması yoluyla, Cainiao Network'ün bu alandaki teknik araştırmasının dünyanın ön saflarına girdiğini belirterek, nihayet araç yolu planlama problemleri için en yetkili değerlendirme platformunda bir dizi dünya rekoru kırdık.
Problem tanıtımı
Araç yolu planlama problemi, yöneylem araştırması optimizasyonu alanındaki en klasik optimizasyon problemlerinden biridir. Bu problemde, belirli mallar için belirli miktarda talebi olan birkaç müşteri bulunmakta ve mallar depodan alındıktan sonra araç müşteriye teslim edilebilmektedir. Müşteri noktaları ve depo noktaları bir dağıtım ağı oluşturur ve araçlar dağıtım görevlerini tamamlamak için bu ağda hareket edebilir. Bu sorunu çözme sürecinde, optimize edilmesi gereken karar değişkenleri, her müşterinin teslimat görevinin hangi araca atanması gerektiği ve her aracın müşterinin teslimat görevini tamamladığı sıradır. Optimizasyon hedefi, kullanılan araç sayısını en aza indirmektir ve Aracın toplam sürüş mesafesi (genellikle araç sayısını en aza indirmek ilk optimizasyon hedefidir).
İ, j dağıtım ağındaki düğümleri (i, j {0,1,2,, N}), 0 depo noktalarını ve diğerleri müşteri noktalarını gösterir) ve k araçları (k {1, 2, ..., K})
Bu, k aracının i noktasından j noktasına gidip gitmediğini gösteren bir karar değişkenidir. Standart araç yolu planlama problemi, aşağıdaki veri planlaması şeklinde tanımlanabilir:
Bunlar arasında (1) ifadesi optimizasyon amacının kullanılan araç sayısını en aza indirmek olduğunu belirtir; (2) ifadesi her noktaya sahip olduğunu ve ihtiyaç duyduğu malları teslim etmekten yalnızca bir arabanın sorumlu olduğunu belirtir; ifade (3) her aracın en çok Bir teslimat yolundan sorumlu; ifade (4), ağdaki akış dengesi koşulunu temsil eder; ifade (5), her araç tarafından dağıtılan malların taşıma kapasitesi sınırını aşmadığını gösterir; ifade (6), soliton oluşumunu önlemektir. Kısıtlamalar.
Araç yolu planlama problemi, lojistik ve üretim alanında yaygın olarak kullanılmaktadır. Bu nedenle, pratik uygulamalarda, standart problemlere ve bazı değişikliklere dayalı bazı değişken problemler de olmuştur. Daha yaygın olanlar şunları içerir:
- CVRP: Teslimat araçlarının taşıma hacmini ve ağırlığını sınırlayan kapasiteli VRP.
- VRPTW: Zaman Pencereli VRP, müşterilerin malların teslim süresi için zaman aralığı gereksinimleri vardır.
- VRPPD: Teslim Alma ve Teslimat ile VRP, paket servis O2O senaryolarında daha yaygın olan teslimat sürecinde araçlar alınabilir ve teslim edilebilir.
- MDVRP: Multi-Depot VRP, dağıtım ağında birden fazla depo vardır ve aynı ürünler birden fazla depodan alınabilir.
- OVRP: VRP açın, aracın teslimat görevini tamamladıktan sonra depoya geri dönmesine gerek yoktur.
- VRPB: Ana taşıyıcılı VRP, araç teslimat görevini tamamladıktan sonra malları almak için geri döner.
Yukarıdaki sorun türleri arasındaki ilişki Şekil 1'de gösterilebilir:
Şekil 1 Çeşitli VRP varyantları
Klasik algoritma
Araç yolu planlama problemi, NP açısından zor olan tipik bir problemdir ve çok zordur. Aynı zamanda, pratik uygulamalardaki büyük değeri nedeniyle, akademik ve endüstriyel çevreler on yıllardır bu tür problemler için optimizasyon algoritmaları araştırmaktadır. Mevcut klasik çözüm algoritmaları iki kategoriye ayrılabilir: kesin çözüm algoritmaları ve sezgisel algoritmalar.
Kesin çözüm algoritmaları açısından en temel yöntem dal ve sınır algoritmasıdır.Teorik olarak en uygun çözümün sınırlı bir sürede elde edilmesini sağlayabilse de, gerçek hesaplamalarda çok büyük bir zaman alıcı durum söz konusudur. Çözümün verimliliğini artırmak için araştırmacılar, algoritmanın çözüm süresini büyük ölçüde azaltan çeşitli Dal ve Kes ve Dal-Kes ve Fiyatlandır yöntemleri önerdiler. Ancak pratik uygulamalardaki büyük ölçekli problemler için (200 puandan fazla problemler gibi), kesin çözüm algoritması yine de makul bir sürede hesaplamayı tamamlayamaz. Bu nedenle araştırmanın büyük bir kısmı sezgisel algoritmalar alanına odaklanmaktadır.
Sezgisel algoritma fikri, çözümü bir dizi sezgisel kural aracılığıyla oluşturmak ve değiştirmek, böylece çözümün kalitesini kademeli olarak iyileştirmektir. VRP için daha klasik sezgisel algoritma Clarke-Wright algoritmasıdır vb. Ek olarak, sürekli keşif ve araştırmanın ardından, meta-sezgisel algoritmanın VRP'yi çözmede etkili ve verimli olduğu kanıtlanmıştır. Benzetilmiş tavlama, tabu arama, genetik algoritma, karınca kolonisi algoritması, değişken komşuluk arama, uyarlanabilir büyük ölçekli komşuluk arama algoritması gibi bazı iyi tasarlanmış meta-sezgisel algoritmalar, VRP'yi çözmede çok iyi performansa sahiptir.
Çaylak araç yol planlama motorunun geliştirme süreci
Aşama 1: Temel temel algoritmaların geliştirilmesi
Araştırma ve geliştirmenin başlangıcında, Cainiao Cangbai'nin akıllı algoritma ekibi, VRP alanındaki ilgili akademik makaleleri ve yazılım ürünlerini tam olarak araştırdı ve sonunda algoritma için temel algoritma olarak Uyarlanabilir Büyük Mahalle Aramasını (ALNS) kullanmaya karar verdi. Motor yapısı. Diğer algoritmalarla karşılaştırıldığında, ALNS algoritmasının avantajları şunları içerir:
- Algoritma çerçevesinin genişletilmesi kolaydır.Standart VRP'yi çözmenin yanı sıra, VRPPD ve MDVRP gibi değişken sorunları da çözebilir;
- Sıradan Yerel Arama algoritmaları ile karşılaştırıldığında ALNS, arama sürecinin her adımında daha geniş bir çözüm alanını keşfedebilir;
- ALNS algoritması, arama işlemi sırasında uygun operatörü uyarlamalı olarak seçebilir, böylece farklı türdeki problem verileri için nispeten kararlı ve iyi çözüm sonuçlarına sahip olabilir;
- ALNS, farklı operatör türlerini tasarlayarak ve uygulayarak, algoritmanın yükseltilmesini ve genişletilmesini kolaylaştıran farklı arama stratejileri uygulayabilir.
Klasik ALNS algoritmasının ana süreci Şekil 2'de gösterilmektedir:
Şekil 2 ALNS algoritmasının ana süreci
Şekil 2'de gösterilen ALNS algoritmasının ana adımları şunlardır:
Çekirdek olarak ALNS algoritması ile çaylak depo akıllı algoritma ekibi, VRP optimizasyon motorunun ilk versiyonunun araştırma ve geliştirmesini tamamladı. Karşılaştırmalı test sonuçları, çözüm etkisinin ve verimliliğinin jsprit gibi uluslararası popüler açık kaynaklı VRP Çözücüsünden önemli ölçüde daha iyi olduğunu göstermektedir. Bu temelde, Cainiao Warehouse'un akıllı algoritma ekibi, şirketin iç ve dış kullanıcılarına daha rahat hizmet verebilmek için motora da hizmet verdi.
Aşama 2: Algoritma sistemini zenginleştirme ve yükseltme
Şirketin iç ve dış kullanıcılarına daha iyi hizmet verebilmek için Cainiao Warehouse'un akıllı algoritma ekibi, VRP optimizasyon motorunun temel algoritma bileşenlerini sürekli olarak zenginleştirdi ve yükseltti. Esas olarak aşağıdaki hususlarda yansıtılmıştır:
1. Mükemmel işlev: Orijinal algoritmanın temel çerçevesi temelinde, Toplama ve Teslimat (araçlar toplanır ve teslim edilir), Çoklu Yolculuk (araçlar teslim edilir) ve diğer problem türleri eklenir; ve gerçek iş problemlerinin soyutlanması yoluyla farklılıklar özetlenir. Optimizasyon hedefi denklem türleri (katmanlı fiyatlandırmanın toplam maliyetini en aza indirme, teslimat süresini en aza indirme vb.) Ve kısıtlamalar (araç seyahat mesafesi sınırı, araç teslimat sipariş numarası sınırı, araç çapraz bölge sayısı sınırı vb.). Böylece çözme motorunun çözebileceği problem daha kapsamlı ve kapsamlıdır.
2. Zengin operatör: Çaylak deposunun akıllı algoritma ekibi, motorun çözüm etkisini ve kararlılığını iyileştirmek için, VRP çözüm motoruna, farklı yerel arama operatörleri (Two-Opt, Three-Opt gibi) gibi daha zengin bir optimizasyon operatörü ekledi. Çapraz Değişim, vb.), Farklı ara sonuç kabul stratejileri türleri (Açgözlü, Simüle Tavlama, vb.).
3. Etkiyi iyileştirin: Cainiao Warehouse'un akıllı algoritma ekibi, motorun çözüm etkisini iyileştirmek için özellikle aşağıdakiler dahil olmak üzere çeşitli algoritmalar denedi:
- Kılavuzlu ejeksiyon araması (GES): Bu algoritma, sürekli olarak bir arabayı silmeye çalışarak ve bu arabanın hizmet verdiği müşterileri diğer araçlara ekleyerek kullanılan araç sayısını azaltır. Bu algoritma, araç sayısını azaltmada çok iyi bir etkiye sahiptir;
- Hızlı yerel arama (FLS): Arama sürecinde, sadece mevcut çözümü geliştirmesi umudu taşıyan mahalle alanları araştırılır, böylece arama hesaplamalarının miktarını büyük ölçüde azaltır ve algoritmanın hızını artırır;
- Rehberli yerel arama (GLS): Arama sürecinde, arama yönünü değiştirmek ve yerel optimuma düşmekten kaçınmak için yerel optimal çözümün belirli özelliklerine cezalar uygulanmaktadır;
- Kenar montaj geçişi (EAX): İki çözüme dayalı yeni bir çözüm üretme yöntemi olan yeni oluşturulan çözüm, ebeveyn bireyin mekansal yapısını iyi bir şekilde miras alabilir;
- Şube ve Fiyat Bazlı Geniş Mahalle Araması: Bu algoritma, VRPTW problemini Kısıtlı Ana Problem ve Alt Problem olarak ayrıştırır. Bunlardan Kısıtlı Ana Problemde, bir dizi uygulanabilir yola dayalı olarak, orijinal problemin çözümü Set Partition problemi çözülerek elde edilir; Altproblemde ise Tabu Search ile yeni bir uygulanabilir yol aranır;
- Yolu Yeniden Bağlama: Bu algoritmanın ana fikri, daha iyi bir çözüm bulmanın mümkün olması için, ilk çözümden kılavuz çözüme doğru kademeli olarak geçerek iki çözüm arasındaki geniş komşuluğu keşfetmektir;
- Hibrit Küme ve Buluşsal Yöntemler: Bu algoritma süper büyük ölçekli problemler için tasarlanmıştır.İlk olarak, müşteri noktaları uygun bir kümeleme algoritması ile kümelenir, böylece orijinal problem çok sayıda küçük ölçekli alt probleme ayrıştırılır ve ardından paralel olarak çözülür ve son olarak alt problemler çözülür. Asıl sorunun çözümü olun.
3. Aşama: Algoritma paralelleştirme yükseltmesi
Sezgisel algoritmaların çoğu için, paralel hesaplama ve birden çok bitişik çözümün kalitesini değerlendirme, birden fazla mahallede arama yapma veya birden çok strateji kullanma gibi paralel hesaplama yoluyla arama verimliliğini ve etkisini doğal olarak artırmak mümkündür. Arama vb. Ve hatta paralel olarak arama yapmak için birden çok algoritma kullanın. Bu nedenle, VRP motorunun çözüm kalitesini daha da iyileştirmek için çaylak deposunun akıllı algoritma ekibi, VRP motoruna paralel bir yükseltme gerçekleştirdi. Bu süreçte, üç set paralel algoritma mimarisi geliştirilmiş ve uygulanmıştır.
Nüfus Adası
Population Island'ın algoritma mimarisi Şekil 3'te gösterilmektedir. Algoritma yürütme sürecinde, paralel olarak hesaplamalar yapan birkaç ada vardır ve her ada bağımsız olarak gelişir.Her birinde bir Master ve birkaç İşçi bulunur.İşçi, belirli arama görevlerinin hesaplanması ve yürütülmesinden sorumludur ve Görevlerin atanmasından ve koordinasyonundan Kaptan sorumludur. Diğer adalar arasındaki iletişim vb. Her belirli sayıda hesaplama adımı, her adanın Kaptanları aynı şekilde iletişim kuracak, arama sürecinde elde edilen bilgileri paylaşacak ve böylece genel arama verimliliğini artıracaktır.
Şekil 3 Nüfus Adası paralelleştirme mimarisi
Paralel Memetik
Paralel Memetic'in algoritma mimarisi Şekil 4'te gösterilmektedir. Tüm algoritma iki aşamaya bölünebilir: İlk aşamanın hesaplanması, kullanılan araç sayısını azaltmaya odaklanır (Rotayı Sil) Bu aşamada, birkaç İşçi paralel olarak hesaplar ve her belirli adımda bir bilgi paylaşmak için birbirleriyle iletişim kurar. İlk aşama bittikten sonra, bir dizi ara sonuç elde edilecek ve bu sonuçlar, ikinci aşamadaki her bir Çalışanın ilk evrim nüfusu olarak hesaplanacaktır. İkinci aşamanın hesaplanması, araç sürüş mesafesini azaltmaya odaklanır (Mesafeyi Azalt) İkinci aşamadaki işçiler de karşılıklı iletişim ve bilgi paylaşımı için bir mekanizmaya sahiptir ve evrim sürecinde ebeveynin seçim mekanizması kontrol edilerek dinamik olarak ayarlanabilirler. Keşif ve Sömürü.
Şekil 4 Paralel Memetik paralelleştirme mimarisi
Merkezi Havuz
Merkezi Havuzun algoritma mimarisi Şekil 5'te gösterilmiştir. Algoritmada, belirli arama görevlerinden sorumlu birkaç İşçi vardır ve aranan çözümler Merkezi Havuza geri gönderilir.Merkezi Yönetici çözümleri sıralar, filtreler ve kümeler.Sonra Merkez Yönetici mevcut Merkezi Havuza dayanır. Ayrıştırma durumu, yeni bir hesaplama görevi oluşturur ve bunu yürütülmesi için İşçiye gönderir. Merkezi Yönetici, çözüm alanının makul bir tanımını yapabilir ve hesaplama görevlerinin yönetimi ve dağıtımı yoluyla Keşif ve Sömürü arasında denge kurabilir, böylece çözümün verimliliğini artırabilir.
Şekil 5 Merkezi Havuz paralelleştirme mimarisi
Sonuçlar elde edildi
Optimizasyon algoritmalarının sürekli yinelemeli yükseltmeleri ve mühendislik mimarisindeki güncellemeler ve iyileştirmeler sayesinde, Cainiao Network'ün araç yolu planlama motoru, iç ve dış müşterilere hizmet verirken teknolojik yağışta önemli sonuçlar elde etti.
VRP algoritmaları alanında, en yetkili değerlendirme ve karşılaştırma platformu, Solomon veri setini (1987'de önerilmiştir) ve Gehring ve Homberger verilerini içeren, Avrupa bağımsız araştırma kurumu SINTEF tarafından başlatılan ve yönetilen Dünyanın En İyi Bilinen Çözümüdür (Bilinen En İyi Çözüm). (1999'da önerilen) 356 test verisinin dünya rekorunu kırdı. Dünyanın en iyi optimizasyon algoritması uzmanları (ör. Jakub Nalepa, D. Pisinger, Yuichi Nagata, vb.) Ve optimizasyon teknolojisi şirketleri (ör. Quintiq, vb.) Bu platformda sürekli olarak yeni dünya rekorları kırıyor ve araç yolu planlama teknolojisini kademeli olarak geliştiriyor. Aşırı itin.
Cainiao Network Warehouse and Distribution'ın akıllı algoritma ekibi, algoritma geliştirme sürecinde bu veri setini her zaman ana algoritma değerlendirme indeksi olarak kullanmıştır. Algoritmaların sürekli yükseltilmesi ve optimizasyonu ile giderek daha fazla veri yaklaşıyor ve hatta dünya rekoruna ulaşıyor.
Sonunda, Eylül 2018'de, depo akıllı algoritma ekibinin algoritması nihayet dünya rekorundan daha iyi sonuçlar elde etti ve platform tarafından doğrulanarak tüm dünyadaki araştırmacılara açıklandı. Nisan 2019'un başından itibaren Cainiao, bu değerlendirme veri setinde 48 dünya rekorunu elinde tuttu ve birçok araştırma ekibi arasında ilk sıralarda yer alan holdinglerin sayısı, Cainiao'nun bu alandaki teknolojisinin dünyanın en üst seviyesine girdiğini gösteriyor. , Cainiaohe Group için büyük bir teknolojik etki kazandı.
Özet ve görünüm
İki yıllık araştırma ve geliştirme sürecinde, çaylak depo akıllı algoritma ekibinin öğrencileri muazzam çabalar ve özenli çabalar sarf ettiler. Aynı zamanda bu süreçte grubun birçok iş bölümünün kardeş ekipleri de algoritma araştırması, mühendislik teknolojisi vb. Konularda birçok güzel profesyonel öneri sundular. Gönülden teşekkürlerimi sunuyorum!
Gelecekte, Cainiao Warehouse'un akıllı algoritma ekibi, VRP motorunu daha güçlü, istikrarlı ve kullanımı kolay optimize edilmiş bir ürün haline getirecek, Cainiao'nun ve grubun çeşitli işlerinin geliştirilmesi için teknik destek sağlayacak ve dışarıdan plan yapacak. Çin'in lojistik endüstrisi için ihracat yapın, güçlendirin ve verimliliği artırın.
