Pulse Algorithm - Rust

This is a Rust implementation of the Pulse algorithm for the Constrained Shortest Path Problem (CSPP). It does not use the bucket implementation of Dijsktra's algorithm, but rather a priority queue.

Reference:

Lozano, L. and Medaglia, A. L. (2013) On an exact method for the constrained shortest path problem. Computers & Operations Research. 40 (1):378-384. DOI: http://dx.doi.org/10.1016/j.cor.2012.07.008

Original implementation (Java) available here

Usage

1. Install Rust and Cargo. Follow the instructions here.
2. Clone this repository.
3. Run the following command to run the program:

cargo run

4. Run the following command to generate the executable:

cargo build -r

You can change the configuration file assets/config.txt to use a different dataset. Check src/main.rs for an example on how to use the crate library. Use the executable to run benchmarks.

Example run

Using the USA Road NY dataset (733846 arcs, 264346 nodes, p=0.1):

Elapsed time: 45.314667ms
Optimal Solution:
Distance: 678151
Time: 750312
Path: [1, 1363, 1358, 1357, 1356, 1276, 1273, 1277, 1269, 1241, 1240, 1235, 956, 953, 955, 957, 958, 959, 960, 962, 1002, 952, 1000, 998, 994, 995, 996, 997, 1011, 6380, 1020, 1019, 1323, 2935, 2936, 2941, 2942, 2949, 2951, 2967, 2968, 2966, 1539, 1538, 3004, 3008, 3056, 3057, 3058, 3059, 3060, 3062, 3042, 3043, 2658, 2650, 2651, 2635, 2574, 2568, 2453, 2452, 2451, 2447, 2446, 6372, 6371, 2410, 2399, 2418, 2143, 2144, 2139, 2131, 2130, 2129, 2087, 2081, 2073, 2075, 2164, 2163, 2162, 2159, 2158, 2160, 71, 61, 60, 1851, 1847, 1846, 1824, 1797, 1787, 1775, 1761, 5526, 5514, 5510, 5507, 5484, 5487, 5486, 5629, 5612, 5611, 4147, 5616, 5596, 5592, 5581, 5579, 5578, 5538, 5537, 5536, 260611, 260610, 260604, 260605, 260607, 260601, 257182, 257185, 257179, 257226, 257224, 257213, 257211, 257212, 257191, 257189, 257190, 256706, 256649, 256637, 256638, 261625, 263806, 260248, 260220, 260015, 259972, 259970, 259960, 259961, 259899, 259900, 259726, 259727, 258603, 258561, 258552, 258549, 258548, 258546, 258544, 258540, 258537, 258498, 258493, 258468, 258467, 258469, 257726, 257674, 257672, 247911, 247910, 247916, 247901, 247782, 247775, 247774, 247773, 247772, 247769, 247768, 247490, 247486, 247483, 247448, 247442, 247432, 247418, 247415, 247409, 247404, 247337, 247335, 247334, 247315, 247299, 247298, 247294, 247293, 247284, 247283, 247282, 245542, 245514, 245513, 245403, 245400, 245401, 245394, 245377, 245378, 245351, 245346, 245331, 245330, 245063, 245060, 244951, 244950, 263765, 263763, 244948, 244947, 244942, 244938, 244868, 244867, 244874, 261350, 244651, 244650, 244861, 244842, 244834, 244831, 244830, 244700, 244697, 244696, 244695, 244677, 244648, 244646, 244664, 244645, 244643, 244642, 244641, 263393, 244635, 244637, 241119, 241113, 241101, 241102, 241048, 241009, 240993, 240217, 261433, 240989, 240988, 240987, 261435, 240605, 240604, 240583, 240078, 240079, 240039, 240037, 240036, 240032, 240030, 240029, 240018, 240009, 240047, 240015, 240007, 240041, 240043, 240040, 239972, 239970, 239981, 239975, 239961, 239958, 239947, 239938, 239937, 239935, 239926, 239925, 239924, 239920, 239918, 239825, 239802, 239798, 239799, 239797, 239796, 239794, 239792, 239786, 239785, 239784, 239783, 239782, 239781, 239746, 239747, 239745, 239770, 239773, 239771, 239772, 239756, 239757, 261210, 239758, 239759, 239754, 239749, 239748, 239750, 239456, 239447, 239445, 239446, 239443, 239441, 239440, 239438, 239410, 239406, 239405, 239391, 239392, 239390, 239389, 239382, 239386, 239384, 239385, 261277, 239954, 239955, 239365, 239360, 239357, 239354, 239351, 239352, 239355, 239324, 239295, 239323, 239322, 239283, 239281, 239280, 239321, 239308, 239306, 239261, 239257, 239256, 239303, 239302, 239301, 239300, 237607, 237604, 237605, 261144, 237592, 237590, 237589, 237588, 237573, 237565, 237562, 237560, 237553, 237552, 237519, 237518, 237516, 237514, 237512, 237513, 237520, 237510, 237511, 263466, 263813, 237505, 237504, 237493, 237492, 237490, 237491, 261474, 237485, 237484, 237482, 237483, 237481, 237430, 237182, 237180, 237165, 237166, 237141, 237139, 237136, 237135, 237091, 237072, 237071, 237063, 237058, 237059, 236899, 236896, 236885, 236886, 236884, 236883, 236864, 236863, 263370, 236861, 236857, 236852, 236847, 236842, 236753, 236754, 261059, 236723, 235714, 235715, 235705, 235712, 235707, 235706, 235702, 235701, 236161, 249126, 249803, 261390, 236160, 236083, 236084, 236078, 236077, 236074, 236075, 236068, 236087, 251122, 251124, 236062, 236060, 236058, 236052, 236055, 236053, 236106, 236107, 236108, 236119, 236123, 236125, 236212, 236219, 264346]

Benchmark

Tested with the USA Road NY dataset described previously in a MacBook Pro M1 with 16GB of RAM.

Rust: 45.314667 ms (rustc 1.80.0)
Java: 89.940708 ms (openjdk version "17.0.11")