### The pulse algorithm: a building block for network optimization

There are a vast amount of tactical and operational problems in transportation and logistics systems that rely on solving shortest paths (and variants) as a building block. The pulse algorithm can be seen as a general framework that can be extended to solve a wide range of routing problems. The idea behind the pulse algorithm is very simple, almost naive. The algorithm is based on the idea of recursively propagating pulses through a network from a start node to an end node. As a pulse traverses the network from node to node, it builds a partial path including the nodes already visited and some attributes associated with that path, such as the cumulative cost or resource consumption. Each pulse that reaches the final node contains all the information for a feasible path from the start to the end node. If nothing prevents the pulses from propagating, the algorithm completely enumerates all possible paths, ensuring that the optimal path is always found. At the core of the algorithm lies the ability to (effectively and aggressively) prune pulses as soon as there is enough evidence that the partial path will not lead to a feasible or improved solution. We have developed variants of the pulse algorithm to solve the Constrained Shortest Path Problem (CSP), the Elementary Shortest Path Problem with Resource Constraints (ESPPRC), the Biobjective Shortest Path Problem (BSP), the Orienteering Problem with Time Windows (OPTW), the Weight Constrained Shortest Path Problem with Replenishment (WCSPP-R), and a variant of the Robust Shortest Path Problem. Also, the pulse algorithm has been used as a module to solve more complex transportation and logistics problems such as the Multi-activity Shift Scheduling Problem and the Bus Rapid Transit Route Design Problem. Other authors have applied it to variants of routing problems for electric vehicles and interdiction problems. |

Photo by sjcockell/ CC BY |

**Contact**: Andrés L. Medaglia

**Related work:**:

- Lozano, L., Duque, D., and Medaglia, A. L. (2016). An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Science. 50(1):348–357.
- Duque, D., Lozano, L. and Medaglia, A. L. (2015). An exact method for the biobjective shortest path problem for large-scale road networks. European Journal of Operational Research. 242:788-797.
- Duque, D., Lozano, L. and Medaglia, A. L. (2015). Solving the Orienteering Problem with Time Windows via the Pulse Framework. Computers & Operations Research. 54:168-176.
- Bolívar, M. A., Lozano, L. and Medaglia, A. L. (2014). Acceleration Strategies for the Weight Constrained Shortest Path Problem with Replenishment. Optimization Letters. 8(8): 2155-2172.
- Lozano, L. and Medaglia, A. L. (2013). On an exact method for the constrained shortest path problem. Computers & Operations Research. 40 (1):378-384.
- Restrepo, M. I., Lozano, L., and Medaglia, A. L. (2012). Constrained network-based column generation for the multi-activity shift scheduling problem. International Journal of Production Economics. 140(1):466-472