Cải thiện hoạt động với tối ưu hóa tuyến đường

Cộng tác viên: Feiko Lai, Michal Szczecinski, Winnie So, Miguel Fernandez

Mỗi ngày, các tài xế GOGOVAN đến các nhà kho trên khắp châu Á để nhận hàng ngàn đơn đặt hàng mà các đối tác kinh doanh của chúng tôi đã yêu cầu chúng tôi giao cho khách hàng của họ.

Các đơn đặt hàng này có thể là một loạt các thứ - từ điện thoại mới được chờ đợi từ lâu, đến món quà kỷ niệm đã được đặt hàng vào phút cuối. Tất cả chúng sẽ có kích thước, hình dạng và trọng lượng khác nhau. Đối với mỗi người trong số họ, sẽ có một người chờ đợi và hy vọng lần này công ty chuyển phát nhanh đến đó đúng giờ

Đây là lý do tại GOGOVAN, chúng tôi làm mọi thứ trong khả năng của mình để đảm bảo việc giao hàng suôn sẻ và kịp thời với chất lượng dịch vụ sẽ làm khách hàng ngạc nhiên. Mọi tuyến giao hàng đều được Nhóm vận hành của chúng tôi lên kế hoạch cẩn thận và kiểm tra kỹ lưỡng, để đảm bảo chúng tôi không bao giờ thất bại.

THẬT SỰ?!

DIDN TIẾNG ANH BẠN CHỈ NÓI RATNG BẠN CÓ NHỮNG ĐƠN HÀNG HÀNG NGÀY?!

Vâng, đó là chính xác.

Trước đây, Nhóm vận hành sẽ phải tự sắp xếp các tuyến giao hàng, thường là vào buổi sáng của xe bán tải và đảm bảo chúng tôi đáp ứng tất cả các yêu cầu về thời gian giao hàng cho ngày hôm đó. Như bạn có thể tưởng tượng, đó không phải là một nhiệm vụ đặc biệt thú vị hay dễ dàng :)

Phải mất một người khoảng 1 giờ để tạo tuyến đường phụ tối ưu cho 100 điểm tham chiếu. Đối với các yêu cầu lớn hơn thế, thời gian này tăng theo cấp số nhân.

Chúng tôi ngay lập tức nhận ra rằng quá trình này chỉ đơn giản là cầu xin một số tự động hóa.

Chúng tôi không chỉ cảm thấy tiếc cho Đội điều hành, những người phải làm công việc trần tục như vậy vào mỗi sáng sớm, mà chúng tôi còn biết rằng khi khối lượng đơn hàng của chúng tôi tăng lên, nhiệm vụ đó sẽ dần trở thành nhiệm vụ bất khả thi. Chúng tôi đã xem nó như một cơ hội để phát triển một công nghệ tiên tiến sẽ trở thành một thành phần cốt lõi của ngăn xếp Khoa học dữ liệu GOGOVAN.

Chúng ta đã bắt đầu như thế nào?

Chúng tôi rất khách hàng và trung tâm điều khiển. Do đó, chúng tôi luôn cố gắng đầu tiên để phân tích một vấn đề từ quan điểm của họ để hiểu cách giải pháp của chúng tôi có thể tác động và mang lại lợi ích cho họ. Sau rất nhiều lần động não, đây là những mục tiêu chúng tôi đã đưa ra:

  • Tất cả các đơn đặt hàng cần phải được giao đúng thời gian.
  • Đảm bảo các trình điều khiển không vội vã thực hiện đúng giờ bằng cách sử dụng thời gian đệm và khoảng cách thời gian thực.
  • Tiết kiệm nhiên liệu bằng cách giảm khoảng cách điều khiển.
  • Giảm thiểu thời gian nhàn rỗi cho các trình điều khiển - không ai thích chờ đợi với một thân cây đầy gói.
  • Cải thiện việc sử dụng xe.
  • Tự động hóa hoàn toàn quá trình.
  • Thuật toán cần có khả năng phát triển cùng chúng tôi - hỗ trợ các loại giao hàng, phương tiện và quốc gia khác nhau.

Khi đã xác định được các mục tiêu chính của mình, chúng tôi quyết định khám phá thế giới của học viện và nguồn mở - ở đó không có điểm nào trong việc khám phá lại bánh xe. Chúng tôi nhận ra rằng vấn đề chúng tôi gặp phải được biết đến rộng rãi là Vấn đề định tuyến xe.

Vấn đề định tuyến xe là gì?

Vấn đề định tuyến xe (VRP) có thể được mô tả là vấn đề tạo ra một tập hợp các tuyến đường tối ưu từ một hoặc nhiều kho đến nhiều khách hàng, chịu một loạt các ràng buộc. Mục tiêu là giao hàng cho tất cả khách hàng, đồng thời giảm thiểu chi phí cho các tuyến đường và số lượng phương tiện.

Vấn đề này là NP-hard, như đã được chứng minh bởi Lenstra và Rinnooy Kan¹. Tuy nhiên, vẫn còn một số phương pháp giải pháp chính xác, sử dụng một nhánh và ràng buộc hoặc lập trình động -, tuy nhiên, như được mô tả trong các bài viết ở trên, chúng dường như chỉ hoạt động cho tối đa 150 điểm.

Hiện tại, các giải pháp tiên tiến thu được bằng cách sử dụng các siêu dữ liệu: Thuật toán di truyền⁴, Tìm kiếm Tabu⁵ và Tối ưu hóa thuộc địa Ant⁶. Đây là những phương pháp chủ yếu được sử dụng trong lĩnh vực hiện nay.

Để đánh giá chuyên sâu về lĩnh vực này, chúng tôi đề xuất luận điểm tuyệt vời này của Xiaoyan Li.

Giải pháp của chúng tôi

Với VRP là một vấn đề được công nhận rộng rãi, thực sự có rất nhiều công ty ngoài kia dường như đang giải quyết vấn đề.

Tuy nhiên, bằng cách nào đó chúng tôi không cảm thấy hài lòng với giải pháp của họ

Chúng tôi chỉ biết rằng nếu chúng tôi kết hợp bí quyết hoạt động, khoa học dữ liệu và chuyên môn nghiên cứu, khối lượng dữ liệu lớn và đóng góp hiện đại của nguồn mở, chúng tôi có thể đi đến một giải pháp nội bộ mạnh mẽ:

  • Được cập nhật hơn, hiệu suất cao hơn và có các thuật toán tùy chỉnh và logic lặp.
  • Là rẻ hơn, hiệu quả hơn và có thể mở rộng hơn.
  • Cho phép phát triển tài sản sở hữu trí tuệ hữu hình và xây dựng lợi thế cạnh tranh xung quanh nó.
  • Cho phép chúng tôi đảm bảo với khách hàng của mình rằng dữ liệu phân phối của họ sẽ không đi xa hơn GOGOVAN.

Đã suy nghĩ về nó khá lâu, chúng tôi quyết định rằng nếu chúng tôi muốn trở thành người dẫn đầu trong lĩnh vực này, chúng tôi cần phải làm theo cách của chúng tôi, không sử dụng một số giải pháp hộp đen.

Vì vậy, chúng tôi đã đi được

Thuật toán đầu tiên

Nhưng chúng tôi đã lao thẳng vào các bài báo học thuật ngay lập tức!

Đầu tiên, chúng tôi tập trung vào việc đưa ra các phương pháp của riêng mình và đánh giá chúng. Quá trình này cho phép chúng tôi hiểu rõ hơn về lĩnh vực này ngay từ đầu và trải nghiệm một số vấn đề phổ biến cho chính chúng tôi (chúng tôi đã không nhận bất cứ điều gì cho phép!). Hơn nữa, điều này đã giúp chúng tôi sau này, vì chúng tôi có thể dễ dàng thấy những ưu và nhược điểm của các phương pháp khác nhau được trình bày trong các bài báo học thuật và đưa ra các chiến lược để kết hợp chúng.

Quá trình như vậy là chìa khóa để hiểu ngay cách gói tuyệt vời này - Công cụ tối ưu hóa của Google - hoạt động. Chúng tôi hiểu rằng những người ở Google đã tiết kiệm cho chúng tôi hàng tháng rằng chúng tôi sẽ dành mã hóa tất cả các thuật toán khác nhau mà chúng tôi muốn thử nghiệm. Họ cho phép chúng tôi xuống phần thú vị nhất ngay lập tức!

Chúng tôi đã dành rất nhiều thời gian để chơi với thư viện đó, thử nghiệm các kịch bản khác nhau và tự mình xem chiến lược nào hiệu quả.

Chúng tôi thích nó rất nhiều, chúng tôi quyết định xây dựng công cụ của chúng tôi xung quanh nó!

Nó có tất cả những gì chúng tôi cần - tính minh bạch, khả năng thử nghiệm, tính linh hoạt và sự hỗ trợ.

Thuật toán đầu tiên đã sẵn sàng. Chúng tôi đã triển khai nó.

Hình 1: Trực quan hóa một trong những nhiệm vụ Tối ưu hóa Tuyến đường đầu tiên của chúng tôi

Tăng trưởng nhanh - làm thế nào để xử lý nhiều đơn hàng hơn?

Phiên bản đầu tiên của Tối ưu hóa tuyến đường hóa ra là một thành công lớn.

Khối lượng đơn đặt hàng được gửi tới Trình tối ưu hóa tuyến đường nhanh chóng tăng từ 500 mặt hàng trên mỗi kho lên hơn 1000. Về mặt lý thuyết, chúng ta sẽ ổn.

Nhưng chúng tôi đã không.

Thời gian chạy thuật toán và sử dụng bộ nhớ của chúng tôi đã tăng vọt nhanh chóng - từ 1 phút và 500 MB đến 10 phút và 5 GB. Khi chúng tôi thử nghiệm nó cho âm lượng cao hơn và cao hơn, cuối cùng chúng tôi đã đạt đến mức tối đa - cho 2000 điểm tham chiếu, mô-đun sử dụng tới 25GB bộ nhớ RAM.

Đó là điều không thể chấp nhận được.

Về cơ bản, chúng tôi có hai lựa chọn:

  • Xây dựng Trình tối ưu hóa tuyến hoàn toàn mới có thể hỗ trợ khối lượng lớn như vậy theo mặc định
  • Tạo một thuật toán mới sẽ chạy trên triển khai hiện tại - có thể là một phương pháp sẽ kết hợp các đơn đặt hàng theo các lô nhỏ hơn sau đó sẽ được gửi tới thuật toán tối ưu hóa chính

Vì chúng tôi thực dụng (và cũng thích xây dựng trên đỉnh công việc tuyệt vời mà chúng tôi đã thực hiện), chúng tôi quyết định tiến hành lựa chọn thứ hai.

Làm thế nào để chúng ta tạo ra các lô nhỏ hơn?

Hãy bắt đầu với một thuật toán phân cụm nổi tiếng - DBSCAN⁸.

Những gì chúng ta có là một phương pháp tiên tiến, nhóm các điểm địa lý lại với nhau. Tuy nhiên, nó có nhược điểm của nó: mỗi cụm phải có cùng bán kính.

Đây không phải là điều chúng tôi muốn vì một lý do đơn giản: một cụm bán kính 1km ở Tsim Sha Tsui có thể chứa 1000 đơn hàng, trong khi các cụm 1km khác ở Pok Fu Lam và Waterfall Bay chỉ có thể chứa 3 đơn hàng.

Các cụm này sẽ thực sự không hiệu quả và không đồng đều

Trong Tsim Sha Tsui, kích thước cụm sẽ quá lớn - chúng tôi sẽ có quá nhiều đơn hàng trong một cụm. Nhưng đồng thời, ở một số khu vực khác, bán kính này sẽ không đủ - các cụm sẽ quá nhỏ và các đơn hàng tương đối gần nhau sẽ nằm trong các cụm riêng biệt.

Đó là lý do tại sao chúng tôi quyết định sử dụng một cách tiếp cận đã được sửa đổi - được gọi là đệ quy-DBSCAN.

Đệ quy-DBSCAN

Nó được xây dựng dựa trên sự sáng chói của DBSCAN, nhưng đồng thời cho phép chúng ta đào sâu hơn vào các khu vực có mật độ điểm cao, trong khi nhóm các đơn đặt hàng từ xa lại với nhau.

Đối với danh sách các đơn đặt hàng, chúng tôi đặt mục tiêu tìm bán kính mà số lượng điểm trung bình sẽ là lớn nhất (nhưng số cụm sẽ cao hơn min_no_cl cluster). Chúng tôi làm như vậy bằng cách sử dụng một thuật toán tìm kiếm nhị phân đơn giản.

Khi chúng tôi đã tìm ra giải pháp tối ưu, chúng tôi sẽ nhập vào các cụm quá lớn và áp dụng cùng một logic cho đến khi chúng tôi đạt đến một điểm khi mỗi cụm chứa ít hơn max_len_cluster.

Sau đó, đối với mỗi cụm, chúng tôi chạy thuật toán Tối ưu hóa Tuyến đường mà chúng tôi đã phát triển bằng Công cụ Tối ưu hóa của Google. Hy vọng, điều này sẽ cho chúng ta một kết quả tương tự nhanh hơn và sử dụng ít bộ nhớ RAM hơn.

Mã giả như sau:

Điểm chuẩn

Chúng tôi đã rất tò mò về cách thức phương thức của chúng tôi sẽ thực hiện, nhưng đồng thời chúng tôi lo lắng rằng đệ quy có thể chạy rất lâu, do đó làm cho thuật toán của chúng tôi không tốt hơn phương pháp cơ bản.

Đó là lý do tại sao lần đầu tiên chúng tôi quyết định xem xét thời gian chạy:

Hóa ra thuật toán đệ quy-dbscan vượt trội hơn nhiều so với phương pháp Công cụ tối ưu hóa của Google. Đồng thời nó không khác nhiều so với thời gian chạy của phương thức dbscan.

Chúng tôi chỉ có thể chạy dbscan cho tối đa 2000 đơn hàng và các công cụ Tối ưu hóa của Google cho 1500 đơn hàng do vấn đề sử dụng bộ nhớ RAM: cả hai phương pháp đều bị hỏng khi bộ nhớ yêu cầu vượt quá 25 GB.

Thời gian chạy rất quan trọng, nhưng điều chúng tôi cũng quan tâm là cách thuật toán mới của chúng tôi thực hiện về tổng khoảng cách và số lượng phương tiện được sử dụng, so với phương pháp cơ bản. Hai biểu đồ cho thấy:

Như chúng ta thấy, phương pháp đệ quy theo sát phương pháp Công cụ tối ưu hóa của Google về cả khoảng cách và số lượng xe. Đồng thời, nó vượt trội hơn phương thức dbscan.

Điều đó có nghĩa là thuật toán mới của chúng tôi nhanh hơn so với đường cơ sở và chất lượng của các giải pháp được tìm thấy là tốt. Ngoài ra, RAM tối đa được sử dụng là chỉ có 1 GB!

Chúng tôi hiểu rồi!

DBSCAN vs Đệ quy-DBSCAN

Chúng tôi cũng muốn chỉ cho bạn cách chính xác đệ quy-dbscan hoạt động tốt hơn cho các điểm tham chiếu từ xa.

Hình 5: So sánh các tuyến DBSCAN và Recursive-DBSCAN. Chúng tôi biết rằng họ vẫn chưa hoàn hảo!

Ở phía trên, bên trái chúng ta có một bản đồ hiển thị một bài tập được tìm thấy bằng thuật toán DBSCAN bình thường. Chúng ta có thể thấy rằng nhiều trình điều khiển chỉ cung cấp một đơn đặt hàng - vì các đơn đặt hàng này là những đơn hàng duy nhất trong lô của họ.

Ở phía bên tay phải, chúng tôi thấy rằng phương pháp đệ quy xử lý vấn đề này khá tốt, bằng cách sử dụng các bán kính khác nhau cho các khu vực khác nhau, nó quản lý để tìm một giải pháp cung cấp tất cả các đơn đặt hàng chỉ bằng 3 xe!

Đây là một hình ảnh hoàn hảo về cách phương thức đệ quy-dbscan tốt hơn cho trường hợp sử dụng của chúng tôi và lý do tại sao chúng tôi chọn sử dụng nó.

Kết luận (còn gọi là TL; DR)

Trong bài viết này, chúng tôi đã trình bày cách tiếp cận của chúng tôi đối với vấn đề định tuyến xe điện dung với Windows thời gian cho số lượng lớn điểm tham chiếu (tối đa 5000). Bằng cách sử dụng phương pháp dbscan đệ quy, chúng tôi có thể giảm đáng kể thời gian chạy và sử dụng bộ nhớ, trong khi vẫn duy trì chất lượng kết quả tương tự như trong phương pháp Công cụ tối ưu hóa cơ bản của Google.

Thuật toán này giúp ích rất nhiều cho nhóm Hoạt động của chúng tôi, giảm hàng giờ làm việc thủ công thông thường xuống vài phút thời gian CPU (và kiểm tra lại kết quả của một người).

Tương lai

Chúng tôi biết rằng công cụ của chúng tôi không hoàn hảo.

Một trong những vấn đề chính là nó vẫn là một phương thức tĩnh, rằng một khi chạy sẽ không tự cập nhật nếu tuyến đường tốt hơn có sẵn hoặc nếu tình huống đường thay đổi. Chúng tôi có một vài lựa chọn trong trường hợp này, một lựa chọn đang thực hiện geohashing như Lyft hoặc một tùy chọn khác đến từ Cơ sở nghiên cứu đối tác của chúng tôi trong Phân tích dữ liệu lớn tại PolyU Hồng Kông.

Mục tiêu của chúng tôi là cải thiện Tối ưu hóa Tuyến đường để nó liên tục theo dõi các trình điều khiển và gửi thông báo nếu các trình điều khiển có nguy cơ không đến đúng giờ với một số bưu kiện - tất cả điều đó để làm cho khách hàng của chúng tôi hài lòng hơn với dịch vụ của chúng tôi.

Hy vọng rằng, bài viết này đã cung cấp cho bạn một số hiểu biết tốt về các vấn đề mà chúng tôi giải quyết tại GOGOVAN. Nếu điều đó nghe có vẻ thú vị với bạn, hoặc bạn chỉ muốn tìm hiểu thêm, xin đừng ngần ngại liên lạc.

Tự nhiên có rất nhiều nền tảng để cải thiện trong tương lai, nhưng chúng tôi hy vọng sẽ chia sẻ một số cách tiếp cận của chúng tôi để châm ngòi cho các cuộc thảo luận và tiến bộ trong một lĩnh vực hấp dẫn để tối ưu hóa các hoạt động hậu cần theo yêu cầu.
Nếu bạn muốn tìm hiểu thêm về Nhóm dữ liệu của chúng tôi, vui lòng xem bài viết của chúng tôi tại đây.
Chúng tôi luôn tìm kiếm các hoạt động ứng dụng hàng đầu và tài năng nghiên cứu ML. Hãy liên lạc nếu quan tâm! (Tại chỗ và từ xa)
Người giới thiệu:
[1] Lenstra, J. K. và Kan, A. H. (1981), Sự phức tạp của các vấn đề định tuyến và lập lịch trình xe. Mạng, 11: 221 Mạnh227. doi: 10.1002 / net.3230110211
[2] Fukasawa, R., Longo, H., Lysgaard, J. et al. Môn Toán. Chương trình. (2006) 106: 491.
[3] Baldacci, R. & Mingozzi, A. Toán. Chương trình. (2009) 120: 347. https://doi.org/10.1007/s10107-008-0218-9
[4] Nagata Y. (2007) Crossover Crossover cho vấn đề định tuyến xe điện dung. Trong: Cotta C., van Hemert J. (chủ biên) Tính toán tiến hóa trong tối ưu hóa kết hợp. EvoCOP 2007. Ghi chú bài giảng Khoa học máy tính, tập 4446. Springer, Berlin, Heidelberg
[5] Bräysy, O. & Gendreau, M. Top (2002) 10: 211. https://doi.org/10.1007/BF02579017
[6] Tan X., Zhuo X., Zhang J. (2006) Hệ thống Ant Colony để tối ưu hóa vấn đề định tuyến xe với Windows thời gian (VRPTW). Trong: Huang DS., Li K., Irwin G.W. (eds) Trí thông minh tính toán và tin sinh học. ICIC 2006. Ghi chú bài giảng Khoa học máy tính, tập 4115. Springer, Berlin, Heidelberg
[7] Xiaoyan Li (2015) Vấn đề định tuyến xe điện dung với Windows thời gian: Một nghiên cứu tình huống về việc thu gom các sản phẩm ăn kiêng trong tổ chức phi lợi nhuận
[8] M. E. Ngày 2 Conf. Khám phá tri thức và khai thác dữ liệu (KDD gợi96), 1996, trang 226 Đến231.