The vehicle routing problem (VRP) is a classic combinatorial optimization problem that is widely used in many fields. It mainly focuses on how to efficiently plan vehicle routes to meet customer needs while minimizing transportation costs.
The underlying logic of VRP is how to organize and call a certain number of vehicles to provide effective services to each customer or collection point. However, depending on factors such as user characteristics and service content, VRP problems are more non-standardized and complex than other types of problems. Major companies in the logistics industry, such as Meituan, JD.com, Cainiao, etc., have studied a series of solutions to the VRP problem based on their own business scenarios. For example, Meituan has launched an intelligent dispatching system based on a big data platform to achieve efficient and dynamic matching of orders and riders to address the key difficulty in food delivery dispatching - the order allocation problem; Dada-JD Daojia uses genetic algorithms in heuristic algorithms to obtain shorter delivery routes; 58 Express uses a staged event-driven approach to improve the algorithm's parallel computing capabilities; Cainiao began to build the ALNS framework in 2016 and integrated VRP into the Greed Solver in 2018. , a general solver is made.
In these studies, large scale, complex scenarios, and timeliness of requirements are all recognized difficulties in VRP problems. Although there are many mature solutions to VRP problems, Jiuzhang Intelligence hopes to provide customers with related needsGet started quickly、Iterate quicklyofHigh cost performancesolution.
Our self-developed Jiuzhang intelligent vehicle route planning and dispatching platform adoptslow codeIn the form, the development threshold is greatly reduced, the development efficiency is increased by more than 90%, and the integration and iteration of various management systems such as APP, CRM, OA, ERP, and WMS can be easily realized to meet the changing business needs. It is easy to maintain and user-friendly, and solves your actual needs at the lowest cost. At the same time, for more complex personalized scenarios, Jiuzhang Intelligence also has a strong "think tank" in the field of operations research and optimization at home and abroad, which can provide customized solutions that flexibly adapt to your business scenarios and provide the best performance.
Based on existing customer needs, Jiuzhang Intelligence has currently built a CVRP model, using "Clustering + exact solver” andheuristic algorithmTwo types of methods to solve. "Clustering + exact solver" technology can convert large-scale CVRP problems into multiple TSP sub-problems, and partition planning can be solved quickly; the heuristic algorithm uses open source algorithm packages and evolutionary algorithm libraries. In actual customer application scenarios, the comparison of the verification effects of our two algorithms and Gurobi is shown in the table below. The heuristic algorithm is better than "clustering + exact formula" and better than directly calling Gurobi for solution.
The route planning effect of quickly solving the problem by calling the heuristic algorithm is as follows:
The Jiuzhang algorithm can be called with one click, automatically schedule according to the vehicle's fuel consumption and vehicle loading rate, and seek the optimization solution with the lowest total cost.
Compared with the original solution, the Jiuzhang algorithm can shorten the driving mileage for customers by 4,760 kilometers, improve the optimization effect by 43%, and shorten the transportation time by 20%.
(Left picture: mileage and duration before optimization, right picture: optimization effect after calling Jiuzhang algorithm)
Jiuzhang Intelligence has launched a test website for vehicle route planning for you to experience. Your feedback is welcome.
Website address: http://47.103.101.234:8000
Username: demo08
Password: %xaauq
The main functions and product features of the test website are as follows:
1. Core functions
-
Data management:Centralized information summary management of requirements, vehicles, and packaging boxes, supporting one-click import.
-
Order processing:Waybill tracking, waybill management, waybill packing list registration, and receipt attachment attachment uploading.
-
Intelligent scheduling: Intelligent packing optimization, intelligent route configuration, and one-click scheduling.
-
Tracking in transit:Track the status of vehicles or waybills in transit in real time, and visualize packing results and transportation routes.
-
Mobile reach:Develop a supporting cargo delivery app to match vehicles and cargo for use by cargo owners and car owners.
2. Product features
(1) The platform is built based on SOA architecture and supports API calls.
The basic architecture is shown in the figure below:
(2) The planning platform provides functions such as data input, route optimization, map display, and report services.
(3) The input data of the planning platform can be called through API or imported into excel. Output vehicle packing results, route information and map display.
Input example:
Output sample:
Vehicle packing results:
Transportation route information:
Map scheduling display:
(4) The supporting mobile phone APP of the cargo man is used to match the vehicles and goods used by the cargo owners and car owners.
(5) Business scenario:
In reality, there are many customization needs for vehicles, customers, targets, and transportation networks. In addition to the existing application platform, Jiuzhang Intelligence can also provide rapid customization services. The following are examples of complex customization scenarios that Jiuzhang can provide in the future:
Other application case display
Jiuzhang Intelligence has solved the diverse needs of customers in different industries and used intelligent decision-making to help enterprises increase value. The following are some typical customers and solutions to VRP problems:
In addition, Jiuzhang Intelligence hopes to contribute its modest efforts to the public welfare cause of rare disease treatment. We plan to launch a free bicycle TSP problem solving algorithm, which can solve the bicycle path planning problem of 300+ demand points in 10 seconds. It is open source for customers with relevant needs (the algorithm link will be attached in the message area). We encourage customers to donate 1% of the cost savings after using the optimization solution to research on rare disease treatment. Hope our little light can illuminate more people in need!
Popular science articles about rare diseases: Listen, these people declare war on 7,000 diseases
If you have any needs for path planning solution optimization, please feel free to inquire.
You can contact the person in charge of Jiuzhang Intelligence through the official website of Jiuzhang Intelligence for details
You are also welcome to join the WeChat group below to learn about Jiuzhang Intelligent’s intelligent decision-making product series
Jiuzhang Intelligent Official Website
http://www.jzlog.cn/
Contact: Zhang Xinjie Mobile: 13311931669 Email: [email protected]
Personal WeChat
Jiuzhang Intelligent Public Account
About the author:
Han Xinyue: A scientific researcher who is studying hard in the field of operations research and optimization~
Liu Sijia: A new operations researcher who is learning machine learning on her own~
[Jiuzhang Intelligent Decision-making Solution] 3D-BPP Visualization Algorithm Solution
1. Some recent developments of Jiuzhang 2. Promotion of some activities
Machine-translated from the Chinese original 【久章智能决策方案】之车辆路径规划（VRP）篇 (published 2024-06-07). WeChat original ↗