VRP - Vehicle Routing Problem; ChatGPT-augmented

ERPNext Stock/Inventory
1

I’m just baffled, so I wanted to share (and by doing so let you know that I’m working at bringing an VRP solver to ERPNext).

The VRP or Vehicle Routing Problem is an extension of the Traveling Salesman Problem (TSP), but with multiple vehicles and a myriad of possible constraints and objective functions. Currently, the integration with Google in ERPNext’s Delivery Trip can already optimize for the TSP, but for that optimization, when dealing with multiple vehicles a solution to the VRP is already required to set up the Delivery Trips efficiently in the first place.

To jump the hurdle of getting started on a Monday evening after a long day, I asked ChatGPT for a kickstart. As the solver, I already had selected GitHub - reinterpretcat/vrp: A Vehicle Routing Problem solver, because it’s written in rust and performance is critical for these solving problems that can easily span 5-10m and 10k and more iterations.

So here’s my starting point.

Prompt:

Please draft a ERPNext assistant, similar to the bank statement import assistant, which applies the vehicle routing problem solver found in github from the user “reinterprecat” and repository “vrp” such that the assistant takes a user selection of ERPNext Delivery Notes and ERPNext Vehicles and configuration flags for the available objective functions and when the user submits the assistent configuration, then it launches the mentioned vrp solver in on of ERPNext background worker processes. After the background worker process has finished solving the problem and presents a solution in GEOJson format, it should be presented to the users as a read-only ERPNext Geolocation Field in the assistent’s view. By the time the solver has finished and the assistent displays the solution to the user in the Geolocation filed, it should also already have created ERPNext Delivery Trips according to the produced solution. Please draft a solution in the form of an ERPNext DocType and associated Python code.

Certainly! I can help you draft a solution using an ERPNext DocType and associated Python code to implement the ERPNext assistant with the vehicle routing problem solver. Here’s an outline of the solution:

  1. Create a new DocType named “VRPAssistant” in ERPNext with the necessary fields, such as “Delivery Notes” (Link field to Delivery Notes), “Vehicles” (Link field to Vehicles), and “Objective Functions” (Checklist field for available objective functions).
  2. Implement a server-side Python function to handle the VRPAssistant configuration and solution generation. This function will be called when the user submits the assistant configuration. Let’s name this function “solve_vrp_assistant”.
# Import necessary modules
import frappe
from vrp_solver import solve_vrp  # Assuming you have the vrp_solver module installed

@frappe.whitelist()
def solve_vrp_assistant(vrp_assistant):
    # Fetch the selected Delivery Notes and Vehicles from vrp_assistant
    delivery_notes = frappe.get_doc("VRPAssistant", vrp_assistant).delivery_notes
    vehicles = frappe.get_doc("VRPAssistant", vrp_assistant).vehicles

    # Fetch the selected objective functions from vrp_assistant
    objective_functions = frappe.get_doc("VRPAssistant", vrp_assistant).objective_functions

    # Create VRP problem instance and solve
    vrp_problem = create_vrp_problem(delivery_notes, vehicles, objective_functions)
    solution = solve_vrp(vrp_problem)

    # Store the solution in ERPNext Geolocation Field
    store_solution_in_geolocation_field(solution)

    # Create ERPNext Delivery Trips according to the solution
    create_delivery_trips(solution)

def create_vrp_problem(delivery_notes, vehicles, objective_functions):
    # Implement logic to create the VRP problem instance
    # using the selected Delivery Notes, Vehicles, and objective functions
    # Return the created VRP problem instance

def store_solution_in_geolocation_field(solution):
    # Implement logic to store the solution in ERPNext Geolocation Field
    # Convert solution to GEOJson format if needed

def create_delivery_trips(solution):
    # Implement logic to create ERPNext Delivery Trips according to the solution
    # Set appropriate fields like source, destination, vehicle, etc.
    # Save the Delivery Trips in the database
  1. In the ERPNext client-side code, create a button or form submit action that calls the solve_vrp_assistant function and passes the VRPAssistant document’s name as a parameter.
  2. You will also need to configure an ERPNext background worker process to handle the execution of the solve_vrp_assistant function. This can be done by creating a new background worker class and specifying the function to be executed when the worker is started. Refer to the ERPNext documentation for more details on setting up background workers.

By following this outline, you can create an ERPNext assistant that allows users to select Delivery Notes, Vehicles, and objective functions, and then solves the vehicle routing problem using the provided solver. The solution is stored in a Geolocation Field and ERPNext Delivery Trips are created based on the solution.

I’d say that’s more than a fair start. VRP in ERPNext still today?!? :smile:

3 Likes
2

Looks like being able to display the final calculated routes to the user for display depends on

3

Progress:

image
image894×274 17.2 KB

image
image932×525 174 KB

image
image891×668 56.9 KB

2 Likes
4

These PRs are currently blocking me:

I’d be absolutely grateful for any tiny bit of priority on them :handshake:

5

During my research, I found this super helpful article [actually: visualization in the article] explaining the various distance measurements for exampl available in scipy.

These distances can give a pretty good first-line estimate of the a more refined distance matrix that can take the actual road grid into account. The actual values can only procured via something like the Google Distance API and that can potentially get expensive as your matrix grows.

It looks like a slightly attenuated Manhatten distance (because on average, shortcuts exist) may be the right approximation.

This is somewhere between the Euclidean and the Manhattan distance and can be calculated via a p-factor between 1 and 2 with the Minkowski distance (scipy.spatial.distance.minkowski).

We can then do a Google Dimension API refinement with a nearest neighbor query (scipy.spatial.KDTree) to (optionally) flesh out some details at a cost, but for nearest-neighbors only.

In the final solution to the VRP, connections between non-nearest-neighbors are unlikely. Which is why with a good Minkowski fallback approximation and a small marginal const query of the Distance API we can probably achieve vastly the same results, even on large matrices, as with a potential full Distance API query.

But depending on the matrix, the actual API usage costs might easily be just a tiny fraction, otherwise.

1 Like
6

I found out that the difference between Google Maps and the Minkowski calculations are so small that it’s not even warranted to query the Google API.

Yes, there will be outliers, but that would be relatively inconsequential in any given scenario of route planning. The algorithm has a conservancy-of-direction bias and as such it’s hard (up to impossible) that because of a (small) distance measurement mistake a tour would detour literally in the opposite direction.

As long as direction is conserved, small distance estimation errors are inconsequential.

And with that, the following code is darn accurate (compared to google maps):

		from pyproj import Transformer
		transformer = Transformer.from_crs(4326,4978)
		
		# transformer
		#
		# <Conversion Transformer: pipeline>
		# Description: Conversion from WGS 84 (geog2D) to WGS 84 (geocentric)
		# Area of Use:
		# - undefined
		
		# transformer.source_crs
		#
		# <Geographic 2D CRS: GEOGCRS["WGS 84 (with axis order normalized for vi ...>
		# Name: WGS 84 (with axis order normalized for visualization)
		# Axis Info [ellipsoidal]:
		# - Lat[north]: Geodetic latitude (degree)
		# - Lon[east]: Geodetic longitude (degree)
		# Area of Use:
		# - name: World.
		# - bounds: (-180.0, -90.0, 180.0, 90.0)
		# Datum: World Geodetic System 1984 ensemble
		# - Ellipsoid: WGS 84
		# - Prime Meridian: Greenwich
		
		# transformer.target_crs
		# 
		# <Geocentric CRS: EPSG:4978>
		# Name: WGS 84
		# Axis Info [cartesian]:
		# - X[geocentricX]: Geocentric X (metre)
		# - Y[geocentricY]: Geocentric Y (metre)
		# - Z[geocentricZ]: Geocentric Z (metre)
		# Area of Use:
		# - name: World.
		# - bounds: (-180.0, -90.0, 180.0, 90.0)
		# Datum: World Geodetic System 1984 ensemble
		# - Ellipsoid: WGS 84
		# - Prime Meridian: Greenwich

		# locations = [(l.lat,l.lng) for l in locations]
		z = 14 # average value in Bogota
		p = 1.06 # based on a bunch of comparative experiments with google maps
		locations = [transformer.transform(l.lat,l.lng, z) for l in locations]
		import scipy.spatial import distance_matrix
		d = distance_matrix(locations,locations,p).ravel()

Note how the EPSG:4978 is used to project WGS84 geodesic coordinates into a three dimensional geocentric coordinate system (in meters).

Because there’s no haversine calculation (as is emulated by the current TSP resolution in the Delivery Trip), that means that going e.g. from Arctica to Antarctica on an euclidean distance (direct line) would go through the middle of the earth.

But that’s a fair limitation for any practical VRP that doesn’t usually span intercontinental “areas of use”. :earth_americas: :sunglasses: