anthony.johnson avatar image
anthony.johnson posted xiawenbo commented

Optimized AGV Dispatching with Google OR-Tools

agvvrp.gifAttached is a sample model that uses Google's OR-Tools python module to find optimal AGV dispatching solutions.

I recently stumbled on Google's OR-Tools, which includes several classes for finding optimal solutions to things like vehicle routing, scheduling, bin packing, etc. Since FlexSim now has a mechanism for easy connection to python, I decided to try and see if/how it could be connected to FlexSim for testing AGV dispatching strategies. I threw together this model just to see how/if the connection can work. All source/destination locations are chosen at random, and work inter-arrival rates are random with a user-defined mean inter-arrival time.

To get this model running on your side:

  • Install a version of python
  • Run the following from the command-line: python -m pip install ortools
  • In FlexSim, make sure your preferences are configured for the correct version of python, and that python is part of your PATH environment variable.
  • Open the model.
  • In the Parameters table, set DispatchMode to 'VRP Solver'.

This model uses the Vehicle Routing Problem solver to find optimal AGV assignment strategies. The main work generation logic is in the 'Work Generation' process flow. At random intervals, work requests arrive. They are assigned to random source and destination locations. Then, when dispatching in 'VRP Solver' mode, the logic calls the optimizeVRP() user command. This command packages the current state of the model into a valid vehicle routing problem, and then passes it to the py_optimizeVRP() user command, which is implemented in python, in the file. The command creates the VRP problem using the OR-Tools classes, and then calls the solver, returning the results. OptimizeVRP() then interprets the results and assigns AGVs as needed. Note that the VRP is re-solved every time new work arrives. You'll see little 'freezes' in the execution of the model, because it is solving the VRP at each work arrival.

Note that the standard Vehicle Routing Problem is slightly different from the problem this model needs optimized:

  • In an AGV model, there’s no depot. Instead AGVs may be currently located anywhere in the warehouse.
  • There’s no ‘depot-loaded’ capacity of an AGV, and no ‘demand’ at customers. The standard VRP is a situation where trucks are loaded at the depot, and then depleted as they visit each customer in the route. This is not present with single-capacity AGVs.
  • When an AGV picks up at an origin location, it must immediately deliver to the destination location.

In order to wrangle the AGV problem into a valid vehicle routing problem that can be solved by OR-Tools, I constructed the problem as follows:

  • I made each AGV’s ‘current location’ a node in the graph
  • The distance from the depot to the AGV’s current location is 0
  • The distance from the depot to any other node in the graph is prohibitively large. This will cause vehicles to always go to their 'current location' first, with 0 cost.
  • The distance from any node in the graph back to the depot is 0
  • A given AGV must visit its current location as part of its route. This can be added as a constraint to the problem in OR-Tools
  • For immediate unload after loading, I initially tried adding this rule as a constraint, but the solver hung when solving. So, instead of graph nodes being locations in the facility, I made graph nodes represent ‘tasks’, i.e. visiting this node means picking up the item AND dropping it off.
  • As such, the ‘cost’ of ‘visiting’ a ‘task’ node is the cost to travel from the ‘destination’ of the previous node to the ‘origin’ of this ‘task’ node, plus the cost to travel from the ‘origin’ of this task node to the destination of this ‘task’ node.

Once I did this, OR-Tools was able to solve the problem 'optimally'. By optimally, I mean it was finding the AGV routing that minimized the maximum 'travel makespan', which is the maximum distance route of all of the AGVs.

Once I had done this, I wanted to compared it with various heuristic-based scenarios. So I set up a 'Closest' dispatch mode. Here, when an AGV finishes a task, it will take up the next task whose pickup point is closest to its current position. I also created a 'FIFO' dispatching mode, which is that work will be dispatched to AGVs always in FIFO order. These three dispatching modes I compared with the experimenter.

My initial experiments showed some interesting results. Most interesting was that in 'VRP Solver' mode, work task time-in-system was relatively high. This is because the objective function completely ignored time in system of the work, and was only optimizing for vehicle travel distance. So some work was being pushed off until much later because vehicles could get better travel distances by pushing it off. To account for this, I added a 'soft upper bound', which is kind of like a 'due date' for the work. Namely, work is due to be finished 800 'meters-of-agv-travel' after it arrives. This was a quick-and-dirty workaround and could certainly be improved, but it did serve to get the time in system for VRP Solver mode down.

Below are some of the resulting experimenter results.

AGVTaskTime - Time from starting a task to finishing it (i.e. a kind of takt time)


The VRP solver performed the best across all scenarios here, and was especially better than the other strategies in low-demand scenarios. This intuitively makes sense. When there are a lot of under-utilized AGVs, the closest and FIFO strategies will always dispatch idle AGVs to do work, which could potentially make them travel long distances. However, the VRP solver can find opportunities to decrease travel distance by waiting to dispatch an AGV that will be near a task in the future, and leave other AGVs idle.

Note that I think the 'closest' strategy only finds the 'closest' next task for an AGV that just finished a task, not the 'closest' idle AGV for an arriving task. Obviously that could be changed for a better performing 'closest' strategy. On the other hand, I think in this model all idle AGVs go back to the same park location, so such a change would require distributed park locations to take advantage of closer idle AGVs.

AGVWorkStaytime - time-in-system for a given AGV task


Here the 'closest' strategy actually performed better than the VRP. This would seem counter-intuitive at first, but upon further evaluation, it does make sense. The VRP, in its current form, only optimizes for total AGV travel distance. It completely ignores job time in system/due dates/etc. So the solver will always assign a route that is shorter even if that route pushes back jobs that have been in the queue for a long time. The solver also re-solves every time a new job arrives. So we may be having scenarios where some jobs are always 'better' to be pushed to the end of the route, and so they keep getting pushed back, resulting in poor time-in-system performance.

The solver does include soft and hard job 'due dates', so we could make adjustments to the problem to make the VRP get better time-in-system results.



AvgAGVUtilization is where the VRP especially shines in low-demand scenarios. It finds opportunities to leave AGVs parked because there will be opportunities for busy AGVs to take up jobs in the future with minimal extra travel overhead, whereas the 'FIFO' and 'Closest' strategies will always dispatch idle AGVs to unassigned jobs, causing extra unnecessary empty travel.

I am still a bit perplexed by the high-demand scenarios though. Here the 'Closest' and 'FIFO' strategies both beat the VRP in the 120/hr and 102/hr scenarios. This probably would warrant further investigation as to why the other strategies do better here. It may be that, in these scenarios, the AGVs cannot keep up with demand. So there is a queue of jobs that is ever-increasing. The VRP solver is optimizing the full plan, meaning it is scheduling job assignments, and finding travel distance minimization opportunities, that are way out into the future. And it is not getting the opportunity to execute those optimized routes because the problem is being re-solved at each job arrival. With an increasing job queue, the 'closest' and 'fifo' strategies might be actually doing better specifically because they are short-sighted. Just take the closest job to you. On the other hand, if we have increasing job queues (i.e. the AGVs can't keep up), then the AGV utilization should be around 100% anyway, which it's not. Anyway, it's something still to churn on.



The throughput per hour indicator tells us whether the AGVs actually kept up with the jobs. If the AGVs were able to keep up with jobs, then the resulting means should be right around the scenario's throughput/hr number. It looks like FIFO got way behind on both the 120/hr and 102/hr scenarios. 'Closest' and VRP both got a little behind in the 120/hr scenarios.

One exciting possibility of using this design is that the python script is not technically dependent on FlexSim. So you can use FlexSim to test your python-based optimization, and then you can deploy that python script in a live setting.

agvvrp.gif (1.2 MiB)
1676649431848.png (147.3 KiB)
1676649571971.png (165.4 KiB)
1676649625252.png (168.0 KiB)
1676649674056.png (137.5 KiB)
· 17
5 |100000

Up to 12 attachments (including images) can be used with a maximum of 23.8 MiB each and 47.7 MiB total.

Youngchul Shin avatar image Youngchul Shin commented ·

I would like to thank you for sharing your valuable output.

There is a question that I would like to ask you.

In this system, new jobs are arriving at an exponential rate.

Then, 'from-to' pairs are randomly generated? In other words, is the location generated randomly when new jobs are created? In that case, am I able to determine where it will occur and what the probability of it will be?

0 Likes 0 ·
Jason Lightfoot avatar image Jason Lightfoot ♦ Youngchul Shin commented ·

The pair of locations are pulled from the EmptyLocations list in the Work Generation process flow:


They are ordered randomly each time and the top pair used as the origin and destination - as such each pair is equally likely to be pulled.

By virtue of the fact that the pair is removed from the list each time, no scenario will arise where two journeys to the same location are ever required at the same time - all AGVwork jobs are to mutually exclusive locations.

0 Likes 0 ·
1681382101703.png (19.3 KiB)
Youngchul Shin avatar image Youngchul Shin Jason Lightfoot ♦ commented ·

Thank you for your reply. Then, how can I adjust the probability of job generation from each location? For example, loc_1 will have high probability of generating new jobs than loc_2.

0 Likes 0 ·
Show more comments
xiawenbo avatar image xiawenbo commented ·

Thank you very much for sharing!

When I was running, there was an error problem. The error was as follows:

Time: 58.248134 the exception: FlexScript exception: Array index out of bounds at MODEL: / Tools/UserCommands optimizeVRP/code

time: 71.033963 exception: FlexScript exception: Setting SoftAssignment label property on object that does not exist at MODEL:/Tools/UserCommands/optimizeVRP/code


Can you provide some guidance?


0 Likes 0 ·
xiawenbo avatar image xiawenbo xiawenbo commented ·

Supplement 1: The running state shown in the figure is the last running state after the error, and all AGVs will not go out to carry the goods

0 Likes 0 ·
xiawenbo avatar image xiawenbo xiawenbo commented ·

Note 2: When I commented out the fourth-to-last line of the optimizeVRP code file, item.SoftAssignment = agv;, only agv13 would move, while the other agvs did not. However, the error message time: 58.248134 exception: FlexScript exception: Array index out of bounds at MODEL:/Tools/UserCommands/optimizeVRP/code still existed.


0 Likes 0 ·
Jason Lightfoot avatar image Jason Lightfoot ♦ xiawenbo commented ·

What did you change to generate this error and which version are you using? Can you post your model? (also consider starting a new post for your case).

0 Likes 0 ·
xiawenbo avatar image xiawenbo Jason Lightfoot ♦ commented ·

I used Flexsim2023. I downloaded the compressed package you released, changed the python version number and environment variables according to your requirements, and directly ran the flexsim file you gave me. However, when I ran VRPsolver, the following error occurred: Time: 58.248134 the exception: FlexScript exception: Array index out of bounds at MODEL: / Tools/UserCommands optimizeVRP/code

time: 71.033963 exception: FlexScript exception: Setting SoftAssignment label property on object that does not exist at MODEL:/Tools/UserCommands/optimizeVRP/code

I think there is a problem in the optimizeVRP code, but I directly used the code you provided, so I am confused.

0 Likes 0 ·
Show more comments
xiawenbo avatar image xiawenbo commented ·

Thank you very much for your answer. May I ask you a few additional questions?

1. When the logistics model is running (as shown in the figure), what do the orange line and red line represent respectively? Are they traction lines or what?

2. When the logistics model is running (as shown in the figure), where are the goods stored and where are the goods stored?

3. Are the goods randomly generated?vrp3.png

0 Likes 0 ·
vrp3.png (28.0 KiB)
Jeanette F avatar image Jeanette F ♦♦ xiawenbo commented ·

Hello @xlawendo,

The red and orange line show control point and control area allocations. This is selected in the AGV network properties.


The items are created from this process flow.


0 Likes 0 ·
1713369533149.png (37.5 KiB)
1713369825335.png (27.0 KiB)
xiawenbo avatar image xiawenbo Jeanette F ♦♦ commented ·

Thank you very much!!!

0 Likes 0 ·



anthony.johnson contributed to this article