The complete research in four takeaways
At 30 kph with no traffic: 24 loops per shift, consuming only 3.34 L at ₱301 — the lowest cost-per-loop in the fleet.
The Suzuki GD gets only 10 loops unassisted. Two scheduled stops raise that to 23 loops — a 130% gain for just 25 min of refueling time.
30 kph is optimal under this model's assumptions: \(\partial F/\partial v = 0\) (fuel per loop does not change with speed) and 30 kph is the maximum safe/allowed patrol speed. Given both conditions, higher speed yields more loops at no extra fuel cost — making the fastest permitted speed the best choice. If either assumption is relaxed, the conclusion must be re-evaluated.
With α = 100, the model redirects 6 corrective path pairs through the highest-incident corridors at zero extra distance.
A two-model lexicographic framework
Finds the shortest closed walk covering every road segment. Solved via Dijkstra + Blossom + Hierholzer algorithms in Python/NetworkX. Result: D* = 9,878.5 m — a mathematical guarantee.
Given D* from Model 1, determines the maximum loops per 8-hour shift for each vehicle under 4 traffic conditions, with optional refueling optimization.
Barangay Tabing-Ilog, Marilao, Bulacan · Graph: 69 vertices, 82 edges · 5 patrol vehicles · 4 traffic conditions
Barangay Tanod units in the Philippines patrol their road networks with limited fuel budgets and, in most cases, no structured method for deciding which routes to take or how many loops a given vehicle can complete in a shift. This paper addresses that gap by developing two linked mathematical models applied to Barangay Tabing-Ilog, Marilao, Bulacan. The first model uses the Chinese Postman Problem (CPP) to derive the shortest closed walk covering every road segment in the barangay, represented as a weighted undirected graph of 69 vertices and 82 edges. The resulting patrol route measures D = 9,878.5 m, the provably minimum distance required to traverse the entire network. A hotspot-weighted edge cost extension (α = 100) further steers corrective path duplication toward the six highest-incident corridors identified from barangay blotter records, without adding any distance to the route.
The second model takes this fixed route as input and determines, for each of five patrol vehicles across four traffic shift conditions, the maximum number of complete loops Cmax achievable within an 8-hour shift given both a time constraint and a fuel constraint. Computations use Python implementations of Dijkstra's Algorithm, the Blossom Algorithm, and Hierholzer's Algorithm via the NetworkX library. Among the vehicles tested, the Bajaj CT110 achieves the best performance: 24 loops at 30 kph under free-flow conditions consuming just 3.34 L, while the Suzuki GD is the most constrained, limited to 10 loops on a single tank but recoverable to 23 loops with two scheduled mid-shift refueling stops. The combined framework follows a lexicographic structure: route distance is minimized first through the CPP, then loop count is maximized given that fixed, fuel-optimal route.
Barangay-level law enforcement in the Philippines depends on Barangay Tanod units to maintain peace and order within their communities, patrolling road networks, responding to emergencies, and deterring criminal activity through visible presence. Republic Act No. 7160 (1991), the Local Government Code, mandates every barangay to sustain a Tanod corps for this purpose.
In practice, these units commonly operate with aging vehicles, constrained fuel budgets, and no systematic basis for deciding how to allocate either resource. Patrol routes tend to be chosen by familiarity rather than formal coverage criteria.
Republic Act No. 7160, the Local Government Code of the Philippines, mandates every barangay to sustain a Tanod corps for peace and order maintenance. In practice, however, these units commonly operate with aging vehicles, constrained fuel budgets, and no systematic basis for deciding how to allocate either resource. Patrol routes tend to be chosen by familiarity rather than by any formal coverage criterion, resulting in wasted distance and uneven attention across the road network. This model directly addresses that operational gap.
1. Which route covers all roads at the lowest possible fuel cost?
2. How many loops can a given vehicle realistically complete within a shift under different traffic conditions?
The road network of Barangay Tabing-Ilog is modeled as a weighted undirected graph $G=(V,E,w)$:
The set of intersections. In Tabing-Ilog, |V| = 69 vertices. Each is numbered v1–v69.
The set of roads connecting intersections. |E| = 82 edges. All roads are two-way → undirected graph.
$w(u,v)$ is the length of the road between intersections u and v, measured from Google Maps.
The CPP finds the minimum-cost closed walk that traverses every edge at least once. When the graph is not Eulerian, certain edges must be repeated. The optimal cost is:
The framework uses a strict two-level priority structure: the primary objective is solved to optimality first; the secondary objective is then optimized only within the set already satisfying the primary. No compromise is permitted.
Level 1 (Primary — non-negotiable): Minimize route distance \(D^*\) via CPP. This simultaneously minimizes fuel per loop \(F_{\text{cycle}} = D \times a_0\). Solved once, never changed.
Level 2 (Secondary): Given D*, maximize loops \(C_{\max}\) per shift. The vehicle model has zero influence on which roads are patrolled or in what order.
A route that is 50 m longer but allows one extra loop is never acceptable.
The fuel consumption model (§1.4), vehicle performance equations (§1.5), two-component fuel model (§1.6), and mid-shift refueling extension (§1.7) are presented in the Vehicle Model tab where they are applied in context.
The two maps below establish the physical and mathematical context for this study. The Hazard / Risk Map (left) is the official barangay document showing flood-risk classification of every road corridor. The Graph Model (right) translates that road network into the weighted undirected graph $G=(V,E,w)$ used by the Chinese Postman algorithm — 69 labelled vertices (green circles) connected by 82 weighted edges, with the patrol depot at vertex 1 (cyan).
The southern corridors along M. Villarica Road and the riverbank streets are classified High Risk — these are also among the top hotspot edges in the patrol model. The Meralco Homes subdivision (right) is Low Risk. This flood map informed the barangay context used to validate incident hotspot data.
Vertex 1 (cyan) is the Command HQ / patrol depot — the start and end point of every loop. All 69 intersections are numbered v1–v69. The 44 odd-degree vertices in this graph require 22 corrective matched pairs, producing the 2,998.4 m overhead above the 6,880.1 m base network length.
Both maps open in the full-screen lightbox viewer. Cross-reference the hazard zones on the left with the vertex numbers on the right — e.g., vertices 44–49 correspond to the high-risk M. Villarica Road corridor visible in red on the official map.
The patrol route of D = 9,878.5 m is the minimum-cost closed walk covering every road segment in Barangay Tabing-Ilog at least once. No alternative closed route that covers all 82 segments can be shorter — this is a mathematical guarantee, not an estimate.
The road network is modeled as G = (V, E, w) with |V| = 69 intersections and |E| = 82 road segments. All main roads in the barangay were verified as two-way through on-site observation, so the graph is undirected.
Several roads near the private market and the elementary school exhibit informal one-way conventions during peak hours. These were treated as bidirectional in the current model. A mixed or directed graph encoding would be more precise but would require the Mixed Chinese Postman formulation rather than the undirected CPP. This is left as a future extension.
| Property | Value |
|---|---|
| Vertices |V| | 69 |
| Edges |E| | 82 |
| Total road length | 6,880.1 m |
| Average edge length | 83.90 m |
| Shortest segment (v59–v60) | 12.51 m |
| Longest segment (v3–v29) | 250.0 m |
| Odd-degree vertices |S| | 44 |
| Even-degree vertices | 25 |
| Is the graph Eulerian? | No |
Table 1: Structural properties of the Tabing-Ilog patrol graph. Edge lengths from Google Maps (2025); graph structure from Baltazar et al. (2026).
Our graph has 44 odd-degree vertices out of 69. Because 44 is even (as guaranteed by the Handshaking Lemma), the CPP matching will always produce exactly 22 pairs. This is guaranteed by the Handshaking Lemma — not a coincidence of the data.
Because 44 of the 69 vertices have odd degree, the graph is not Eulerian and a simple closed walk cannot traverse every edge exactly once. The CPP determines which edges to repeat by solving a minimum-weight perfect matching on those 44 odd-degree vertices.
Collect S = {v ∈ V : deg(v) is odd}. For Tabing-Ilog, |S| = 44, confirming 22 matched pairs will result.
Dijkstra's Algorithm computes the 44×44 pairwise distance matrix. The Blossom Algorithm then finds the minimum-weight perfect matching M* on the complete auxiliary graph K₄₄. For each matched pair, the shortest-path edges are duplicated in the augmented multigraph G'.
Every vertex in G' now has even degree, so an Eulerian circuit is guaranteed to exist. Hierholzer's Algorithm extracts this circuit beginning at v1 (Command HQ).
| Component | Metres | Kilometres |
|---|---|---|
| Original network (82 edges) | 6,880.1 | 6.8801 |
| Repeated paths (22 matched pairs) | 2,998.4 | 2.9984 |
| Minimum CPP Patrol Route | 9,878.5 | 9.8785 |
Table 3: Distance breakdown. The 43.58% overhead is unavoidable — not planning inefficiency, but the mathematical minimum forced by 44 odd-degree vertices.
The 43.58% overhead (2,998.4 m extra) is unavoidable given this road topology. However, adding a small connector road between certain dead-end segments would reduce odd-degree vertices, lowering the required matching overhead. A future study could identify which road additions produce the greatest reduction in |S| per metre of new construction.
To steer corrective path duplication toward higher-risk corridors, the pure distance weight on each edge is replaced with a composite cost:
Every edge is traversed at least once regardless of weighting (CPP guarantees this). The hotspot extension controls which edges receive a second traversal through corrective matching — concentrating additional traversals on highest-incident corridors. At α = 100, 6 of 22 corrective path pairs are redirected. Total route distance stays at D* = 9,878.5 m.
The incident counts $n(u,v)$ used in the hotspot formula are drawn directly from the Barangay Tabing-Ilog official blotter records for 2024. Each entry in the blotter corresponds to a reported incident (theft, disturbance, accident, etc.) that was localized to a specific road segment. The maximum recorded incidents on any single edge was Nmax = 10 (edge 24–25), which serves as the normalization denominator. This means the model embeds the barangay's own operational history — not external crime estimates — directly into the route structure, and can be recalibrated annually as new blotter records accumulate.
The three event types — theft, disturbance, and road-related emergency — are aggregated into a single count n(u,v). These types have different spatial determinants: road-related emergencies correlate with road geometry and traffic volume, whereas theft and disturbance correlate with land use, pedestrian activity, and lighting. Treating them as equivalent inputs is a simplification. Disaggregating by event type and computing separate hotspot layers would allow the barangay to target different patrol objectives simultaneously. This is left as a future extension; the aggregated score is retained because the blotter does not record sufficient volume per category to support reliable per-type weighting.
| Edge | Incidents | h(u,v) |
|---|---|---|
| (24, 25) | 10 | 1.00 |
| (21, 22) | 8 | 0.80 |
| (20, 21) | 7 | 0.70 |
| (14, 21) | 6 | 0.60 |
| (13, 14) | 5 | 0.50 |
| (22, 24) | 4 | 0.40 |
| (17, 22) | 3 | 0.30 |
| (15, 17) | 2 | 0.20 |
| (12, 23) | 2 | 0.20 |
| (18, 25) | 1 | 0.10 |
Table 2: Incident data and normalized hotspot scores h(u,v). Source: Barangay Tabing-Ilog official blotter records (2024). N_max = 10 (edge 24–25, the highest-incident corridor). All incident counts reflect formally logged Tanod reports — not estimated figures.
Systematic testing across α ∈ {0, 50, 100, 150, 200, 250, 300} shows:
| Alpha (α) | Pairs Redirected | Extra (m) | Total Route (m) | Overhead % |
|---|---|---|---|---|
| 0 | 0 | 2,998.4 | 9,878.5 | 43.58% |
| 50 | 3 | 2,998.4 | 9,878.5 | 43.58% |
| 100 ✓ | 6 | 2,998.4 | 9,878.5 | 43.58% |
| 200 | 6 | 2,998.4 | 9,878.5 | 43.58% |
| 250 | 6 | 3,045.2 | 9,925.3 | 44.26% |
| 300 | 6 | 3,112.8 | 9,993.0 | 45.24% |
α = 100 is the recommended setting: lowest penalty achieving full redirection without inflating route distance. The stable zone is α ∈ [100, 200].
The following formulations define the mathematical framework used throughout this tab. They establish how fuel consumption, cycle time, and maximum loops are computed for each vehicle and shift condition.
Fuel consumption is modeled as proportional to distance at a constant rate \(a_0\;[\text{L/km}]\). This is standard for combustion engines at constant speed on flat roads.
The uniform-multiplier structure applies the same congestion factor to both time and fuel. In reality, idling at low speed burns fuel proportional to time, not distance, so the model underestimates congestion fuel penalty — particularly for the Suzuki GD's carbureted engine. Field GPS calibration of \(a_0\) is identified as the most important next step.
Speed $v$ does not appear in $F_{\text{cycle}}$. Fuel per loop is completely independent of how fast the vehicle drives. Whether you patrol at 10 kph or 30 kph, you burn the same fuel per loop. Faster is always better — more loops, same cost.
The simplified distance-proportional model treats congestion as slower travel over the same distance. In reality, fuel consumption under congestion has two physically distinct components:
The two-component model requires per-vehicle idle fuel rates $a_{\text{idle}}$, which are not available from manufacturer datasheets and must be measured under actual patrol conditions using a fuel-flow sensor or GPS-logged fuel consumption data. Until field calibration is carried out, the simplified model ($F_{\text{cycle}}=D_{\text{km}}\times a_0\times\beta_s$) is used for all computations, with the explicit acknowledgment that it underestimates congestion-period fuel costs. For afternoon-shift results in particular, Suzuki GD fuel figures should be treated as lower bounds.
The two-component model also has two important consequences: (1) fuel per loop is no longer speed-independent under congestion — higher speed reduces idle time ΔT, thereby reducing the idle penalty; (2) the idle penalty is proportionally larger for carbureted engines (Suzuki GD) than for fuel-injected ones.
The patrol fleet consists of five vehicles. Their fuel economy and tank capacities determine the base fuel rate $a_0=\dfrac{1}{e}\;[\text{L/km}]$ — the single most important per-vehicle input.
The Bajaj CT110 (71 km/L) is more than 6× more fuel-efficient than the Suzuki GD and APV. The Suzuki GD combines poor economy (11 km/L) with a small tank (9.2 L) — making scheduled refueling a necessity. The Suzuki APV shares the GD's economy but carries a 46 L tank, making shift duration the binding constraint instead.
All fuel economy figures are taken from manufacturer specifications under standardized test conditions. Real-world urban fuel economy for motorcycles and light vehicles in stop-start barangay patrol typically runs 15–30% below these figures. The loop counts and fuel costs in the results should therefore be treated as optimistic upper bounds. A 20% economy penalty applied uniformly across the fleet would reduce the Bajaj CT110's no-traffic loop count from 24 to approximately 20, and the Aerox's from 22 to 18. Field measurement of actual fuel consumption over a representative patrol shift is strongly recommended before relying on specific figures for budget planning.
| Shift | \(p_s\) | \(\beta_s\) | Interpretation |
|---|---|---|---|
| No Traffic | 0% | 1.00 | Baseline — no overhead |
| Morning | 20% | 1.20 | All times and fuel ×1.20 |
| Afternoon | 40% | 1.40 | Worst case — all metrics ×1.40 |
| Night | 5% | 1.05 | Near-baseline, lightest overhead |
Traffic multiplier \(\beta_s = 1 + p_s\) uniformly scales both \(T_{\text{cycle}}\) and \(F_{\text{cycle}}\). These are barangay-level field estimates without GPS backing — should be treated as planning estimates.
| Vehicle | Tank (L) | \(F_{\text{cycle}}\) base | \(C_{\text{empty}}\) | Recommended Role |
|---|---|---|---|---|
| Aerox (Chief) | 5.5 | 0.247 L | 22 | Supervisory patrol |
| Bajaj CT110 | 11.0 | 0.139 L | 79 | Primary loop patrol |
| Suzuki GD | 9.2 | 0.898 L | 10 | Emergency response only |
| Suzuki APV | 46.0 | 0.898 L | 51 | Support / transport |
| Nissan NV350 | 65.0 | 0.760 L | 85 | Multi-crew rapid response |
Table 16: Fleet operational roles based on model analysis.
• Traffic multiplier \(\beta_s\) is uniform, not link-specific. The model scales all edges by the same factor \(p_s\), but real congestion clusters at specific intersections and arterial roads. A future extension could assign individual β values per edge from GPS traces.
• Congestion penalties \(p_s \in \{0\%,\,20\%,\,40\%,\,5\%\}\) are barangay-level field estimates with no instrument backing. No published traffic study specific to Marilao municipal roads was identified to corroborate these figures. All loop counts and fuel figures should be treated as planning-level estimates, not guarantees. A 10% overestimate of the afternoon penalty (\(p_s = 0.44\) instead of \(0.40\)) increases \(F_{\text{cycle}}\) by 2.9% for all vehicles and costs the most fuel-constrained vehicles one additional loop — but the qualitative conclusions remain stable.
• Idle fuel burn under congestion is underestimated. The model's \(F_{\text{cycle}}\) formula is distance-proportional \((F = D \times a_0 \times \beta_s)\). In reality, at low speeds and during stops, carbureted engines (like the Suzuki GD) burn fuel proportional to time idling, not distance traveled. This means the model systematically underestimates fuel consumption during heavy afternoon congestion — the GD in particular may exhaust its tank sooner than the model predicts.
• Refueling station not modeled as a graph node \((\delta_r = 0\) assumed). The current model treats each refueling stop as a time cost only \((t_r = 12.5\text{ min})\), with no detour distance added. In reality, the patrol vehicle must navigate to the nearest gas station. If the detour plus stop time exceeds approximately 13 minutes per visit, the GD's achievable loop count drops from 23 to 22. The nearest station should be verified against the route before adopting the refueling schedule operationally.
• Emergency dispatch times via Dijkstra are optimistic lower bounds. Dijkstra computes geometric shortest paths at constant speed. Actual emergency response times are longer because acceleration from rest, deceleration before stops, U-turns, and intersection queuing delays are not modeled. The dispatch estimates should be read as best-case minimums, not realistic averages.
• Route \(D = 9{,}878.5\text{ m}\) is valid only for the current road network. Any new road, closure, or reclassification requires re-solving the full CPP.
The critical speed \(v^*\) is the patrol speed at which the time ceiling exactly meets the fuel ceiling. Vehicles with \(v^* < 30\) kph are fuel-limited at the recommended speed; others are time-limited.
| Vehicle | \(C_{\text{fuel}}\) (one tank) | \(v^*\) (kph, no traffic) | At 30 kph |
|---|---|---|---|
| Aerox (Chief) | 22 | 27.2 | Fuel-limited |
| Bajaj CT110 | 79 | 97.6 | Time-limited ✓ |
| Suzuki GD | 10 | 12.3 | Fuel-limited |
| Suzuki APV | 51 | 63.0 | Time-limited |
| Nissan NV350 | 85 | 105.0 | Time-limited |
Vehicles with \(v^* < 30\) kph (Aerox, Suzuki GD) are fuel-limited at the recommended patrol speed. Only refueling or a larger tank can improve their coverage.
All algorithms are implemented in Python using the NetworkX library. The full pipeline consists of 12 code modules covering graph construction, CPP solving, vehicle performance, and emergency dispatch analysis. The complete pipeline runs in under 10 ms on standard hardware.
| Code | Algorithm / Module | Complexity | Role in Pipeline |
|---|---|---|---|
| 1 | Graph Construction | O(V + E) | Build G = (V,E,w) with 69 vertices, 82 edges; find 44 odd-degree vertices |
| 2 | Dijkstra's Algorithm | O((V + E) log V) | Compute pairwise shortest paths for all 44 odd-degree vertices → 22×22 distance matrix |
| 3 | Blossom Algorithm + Hierholzer | O(nm log n) + O(E) | Minimum-weight perfect matching on K₄₄; extract Eulerian circuit from G' |
| 4 | CPP Result Verification | O(E) | Confirm D* = 9,878.5 m, 22 matched pairs, overhead = 2,998.4 m |
| 5 | Traffic Multiplier Model | O(1) | Define \(\beta_s = 1 + p_s\) for all four shift conditions |
| 6 | Fuel Economy Functions | O(1) | Derive \(a_0 = \tfrac{1}{e}\) for each vehicle; confirm speed-independence of \(F_{\text{cycle}}\) |
| 7 | Core Performance Functions | O(1) per vehicle | \(T_{\text{cycle}}\), \(F_{\text{cycle}}\), \(C_{\max}\) — 60 combinations (5 vehicles × 3 speeds × 4 shifts) |
| 8 | Mid-Shift Refueling Optimizer | O(n), max 4 iter | Find optimal stop count \(n^*\) for fuel-limited vehicles |
| 9 | Full Results Matrix | O(V·S) | Print all \(C_{\max}\) values, binding constraints, and per-shift fuel costs |
| 10 | Constraint Verification | O(V·S) | Assert all \(C_{\max}\) values satisfy both the time constraint and fuel constraint |
| 11 | Emergency Dispatch (Dijkstra) | O((V + E) log V) | Shortest-path response times for 5 incident scenarios × 3 traffic conditions |
| 12 | Critical Speed v* Analysis | O(V) | Compute crossover speed \(v^*\) separating time-limited from fuel-limited regimes |
Python 3.x · NetworkX (graph algorithms: Dijkstra, Blossom, Hierholzer) · math (floor, inf) · itertools (combinations for odd-node pairing). No non-standard dependencies beyond NetworkX. Install with: pip install networkx
The first module builds the road network of Barangay Tabing-Ilog as a weighted undirected graph G = (V, E, w) using NetworkX. Every road intersection becomes a vertex and every road segment becomes an edge whose weight is the length in metres measured from Google Maps. After construction the code computes three structural properties that determine whether the CPP requires edge repetition: the degree sequence, the count of odd-degree vertices, and the total sum of all edge weights (the theoretical minimum patrol distance if the graph were Eulerian). In Tabing-Ilog, 44 of the 69 vertices have odd degree, so 22 corrective matchings are required before Hierholzer's algorithm can run.
Euler's theorem states a connected graph has an Eulerian circuit (a closed walk covering every edge exactly once) if and only if every vertex has even degree. With 44 odd-degree vertices, Tabing-Ilog's graph is not Eulerian — some edges must be traversed more than once. The CPP finds the minimum-cost set of edges to duplicate so that all degrees become even.
import math
import networkx as nx
# ── GLOBAL CONSTANTS ──────────────────────────────────────────────
D_KM = 9.8785 # CPP-optimal route distance (km) — computed by Code 3
T_MAX = 480 # 8-hour patrol shift in minutes
SPEEDS = [10, 20, 30] # candidate patrol speeds (kph)
# ── COMPLETE EDGE LIST: all 82 road segments (u, v, length_m) ─────
EDGES = [
(1, 2, 158.64), (1, 29, 54.05), (2, 3, 42.40), (2, 9, 78.25),
(3, 4, 78.25), (3, 8, 75.89), (3, 29, 250.00), (5, 8, 47.00),
(6, 10, 88.06), (7, 11, 89.03), (8, 9, 43.10), (9, 10, 40.00),
(10, 11, 33.10), (11, 12, 92.00), (12, 13, 38.00), (12, 23, 239.31),
(13, 14, 35.00), (13, 20, 195.00), (14, 15, 33.44), (14, 21, 180.00),
(15, 16, 18.46), (15, 17, 130.00), (16, 18, 110.00), (17, 18, 29.00),
(17, 22, 33.79), (18, 19, 31.87), (18, 25, 130.00), (19, 26, 140.00),
(20, 21, 60.00), (21, 22, 36.14), (21, 24, 85.00), (22, 24, 100.00),
(23, 24, 130.00), (24, 25, 49.00), (24, 27, 42.00), (25, 26, 30.50),
(26, 28, 34.32), (27, 28, 84.50), (29, 30, 150.00), (30, 31, 160.00),
(30, 37, 63.60), (31, 32, 50.30), (32, 33, 16.82), (32, 34, 14.88),
(33, 35, 26.00), (35, 36, 40.20), (37, 38, 60.00), (37, 43, 31.07),
(38, 39, 152.95), (39, 40, 173.70), (39, 41, 183.80), (41, 42, 70.35),
(41, 44, 180.00), (43, 44, 118.40), (44, 45, 53.00), (45, 46, 19.36),
(45, 48, 69.12), (46, 47, 56.89), (47, 48, 60.39), (48, 49, 36.85),
(49, 50, 150.00), (49, 51, 213.00), (51, 52, 170.00), (51, 53, 69.78),
(53, 54, 142.31), (53, 55, 112.41), (55, 56, 79.20), (55, 64, 93.00),
(56, 57, 39.86), (56, 58, 140.00), (58, 59, 73.48), (59, 60, 12.51),
(59, 63, 13.57), (60, 61, 67.35), (61, 62, 43.41), (62, 63, 76.57),
(64, 65, 110.00), (64, 69, 82.24), (65, 66, 65.59), (66, 67, 54.27),
(66, 68, 49.68), (68, 69, 69.12),
]
# Total base network length: 6,880.1 m (sum of all 82 edge weights)
# ── BUILD GRAPH ───────────────────────────────────────────────────
G = nx.Graph()
for u, v, w in EDGES:
G.add_edge(u, v, weight=w)
# ── STRUCTURAL ANALYSIS ───────────────────────────────────────────
total_length = sum(w for _,_,w in EDGES)
odd_nodes = [v for v in G.nodes() if G.degree(v) % 2 == 1]
even_nodes = [v for v in G.nodes() if G.degree(v) % 2 == 0]
print(f"Vertices : {G.number_of_nodes()}") # → 69
print(f"Edges : {G.number_of_edges()}") # → 82
print(f"Base length : {total_length:.1f} m") # → 6,880.1 m
print(f"Odd-degree : {len(odd_nodes)}") # → 44 (must be even — Handshaking Lemma)
print(f"Even-degree : {len(even_nodes)}") # → 25
print(f"Matching pairs needed: {len(odd_nodes)//2}") # → 22
print(f"Is Eulerian: {nx.is_eulerian(G)}") # → False (requires all even degrees)
print(f"Is connected: {nx.is_connected(G)}") # → True (required for CPP)Before the Blossom matching can run it needs to know the shortest-path distance between every pair of the 44 odd-degree vertices. This module runs Dijkstra's algorithm on G for each odd-degree vertex as source, collecting the 44×44 distance matrix. Only the upper triangle (22 pairs from C(44,2) = 946 combinations) is stored, since the graph is undirected. Dijkstra is called once per odd vertex using NetworkX's single-source shortest-path function; the result is a dictionary of distances to every reachable node, from which the inter-odd distances are extracted.
The Blossom Algorithm needs a complete weighted graph K₄₄ where the edge weight between two odd vertices is the shortest-path distance through the full road network — not the direct edge weight (which may not even exist). Dijkstra produces exactly these shortest-path distances. All 82 edge weights are non-negative, satisfying Dijkstra's requirement.
import itertools
import networkx as nx
# odd_nodes: list of 44 odd-degree vertices from Code 1
# G : the weighted NetworkX graph from Code 1
# ── COMPUTE ALL-PAIRS SHORTEST PATHS AMONG ODD NODES ─────────────
# Run Dijkstra from every odd vertex as source
dist_dict = {}
for v in odd_nodes:
# Returns {target: distance} for all reachable nodes
dist_dict[v] = nx.single_source_dijkstra_path_length(G, v, weight="weight")
# ── BUILD UPPER-TRIANGLE DISTANCE MATRIX ─────────────────────────
# Only need C(44,2) = 946 unique pairs (undirected graph)
dist_matrix = {}
for u, v in itertools.combinations(odd_nodes, 2):
dist_matrix[(u, v)] = dist_dict[u][v]
print(f"Unique odd-node pairs: {len(dist_matrix)}") # → 946
# ── VERIFICATION: spot-check two known pairs ──────────────────────
# Shortest path from depot v1 to v24 (Medical Emergency site)
d_1_24 = nx.shortest_path_length(G, 1, 24, weight="weight")
p_1_24 = nx.shortest_path(G, 1, 24, weight="weight")
print(f"d(v1, v24) = {d_1_24:.2f} m, path = {p_1_24}")
# Shortest path from checkpoint v30 to v66 (scenario 5)
d_30_66 = nx.shortest_path_length(G, 30, 66, weight="weight")
print(f"d(v30, v66) = {d_30_66:.2f} m")This is the core CPP solver. It takes the 44 odd-degree vertices and their pairwise Dijkstra distances, constructs an auxiliary complete weighted graph K₄₄, and invokes NetworkX's minimum-weight perfect matching (which internally uses Galil, Micali and Gabow's implementation of Edmond's Blossom Algorithm). The matching returns 22 vertex pairs whose total corrective path weight is minimal — this is the CPP overhead. Each matched pair's shortest path is then duplicated in an augmented multigraph G', making all 69 vertices even-degree. Hierholzer's algorithm then finds the Eulerian circuit starting from the depot vertex v1, producing the full 9,878.5 m patrol route.
22 matched pairs · total overhead = 2,998.4 m · total patrol distance = 9,878.5 m · circuit traverses all 82 edges, starts and ends at v1.
import networkx as nx
# ── STEP 1: BUILD AUXILIARY COMPLETE GRAPH K₄₄ ───────────────────
# K has one node per odd-degree vertex; edge weight = shortest-path distance
K = nx.Graph()
for i, u in enumerate(odd_nodes):
for j, v in enumerate(odd_nodes):
if i < j:
K.add_edge(u, v, weight=dist_matrix[(u, v)])
# K has 44 nodes and C(44,2)=946 edges
# ── STEP 2: MINIMUM-WEIGHT PERFECT MATCHING (BLOSSOM ALGORITHM) ──
# Returns a set of 22 (u,v) pairs whose total weight is minimised
matching = nx.min_weight_matching(K)
overhead = sum(dist_matrix[(min(u,v), max(u,v))] for u, v in matching)
print(f"Matched pairs : {len(matching)}") # → 22
print(f"CPP overhead : {overhead:.1f} m") # → 2,998.4 m
print(f"Total D* : {6880.1 + overhead:.1f} m") # → 9,878.5 m
# ── STEP 3: BUILD AUGMENTED MULTIGRAPH G' ─────────────────────────
# Duplicate the shortest-path edges for each matched pair
G_aug = nx.MultiGraph(G) # copy of G; MultiGraph allows parallel edges
for u, v in matching:
path = nx.shortest_path(G, u, v, weight="weight")
for i in range(len(path) - 1):
a, b = path[i], path[i + 1]
G_aug.add_edge(a, b, weight=G[a][b]["weight"])
# G' now has 118 edges (82 original + 36 duplicated)
# All 69 vertices now have even degree → G' is Eulerian
# ── STEP 4: EXTRACT EULERIAN CIRCUIT (HIERHOLZER'S ALGORITHM) ─────
# NetworkX uses Hierholzer's O(E) algorithm internally
circuit = list(nx.eulerian_circuit(G_aug, source=1))
total_dist = sum(G[u][v]["weight"] for u, v in circuit
if G.has_edge(u, v)) \
+ sum(G[u][v]["weight"] for u, v in circuit
if not G.has_edge(u, v)) # duplicated edges
# Simpler: sum from G_aug directly
total_dist = sum(data["weight"]
for u, v, data in G_aug.edges(data=True))
print(f"Circuit length : {total_dist:.1f} m") # → 9,878.5 m ✓
print(f"Circuit edges : {len(circuit)}") # → 118
print(f"Starts/ends at : v{circuit[0][0]} / v{circuit[-1][1]}") # → v1 / v1After solving the CPP this module performs three independent checks to confirm the result is correct. First, it verifies every vertex in G' has even degree. Second, it confirms the total circuit distance equals 9,878.5 m. Third, it checks every original edge in G appears at least once in the circuit — ensuring full coverage. These assertions act as a mathematical guarantee: if any of them fail, the CPP solution is invalid and the patrol route cannot be certified as covering the entire road network.
import networkx as nx
# ── CHECK 1: All vertices in G' must have even degree ─────────────
odd_in_aug = [v for v in G_aug.nodes() if G_aug.degree(v) % 2 != 0]
assert len(odd_in_aug) == 0, f"G' still has {len(odd_in_aug)} odd-degree vertices!"
print("✓ CHECK 1 PASSED: All vertices in G' have even degree")
# ── CHECK 2: Total circuit distance = 9,878.5 m ───────────────────
circuit_dist = sum(data["weight"] for _, _, data in G_aug.edges(data=True))
assert abs(circuit_dist - 9878.5) < 0.1, f"Distance mismatch: {circuit_dist:.1f}"
print(f"✓ CHECK 2 PASSED: D* = {circuit_dist:.1f} m")
# ── CHECK 3: Every original edge is covered at least once ─────────
circuit_edges = set()
for u, v in circuit:
circuit_edges.add((min(u,v), max(u,v)))
uncovered = []
for u, v, _ in EDGES:
if (min(u,v), max(u,v)) not in circuit_edges:
uncovered.append((u, v))
assert len(uncovered) == 0, f"Uncovered edges: {uncovered}"
print(f"✓ CHECK 3 PASSED: All 82 edges covered")
# ── SUMMARY ───────────────────────────────────────────────────────
base = sum(w for _,_,w in EDGES)
overhead_m = circuit_dist - base
print(f"Base network : {base:.1f} m") # → 6,880.1 m
print(f"CPP overhead : {overhead_m:.1f} m") # → 2,998.4 m (43.58% of base)
print(f"Matched pairs : {len(matching)}") # → 22
print(f"Circuit start : v{circuit[0][0]}") # → v1 (patrol depot)The model accounts for real-world congestion by applying a traffic multiplier \(\beta_s = 1 + p_s\) to both travel time and fuel consumption, where \(p_s\) is the fractional congestion penalty for shift \(s\). Four shift conditions are defined: free-flow (no congestion, β = 1.00), morning rush (p = 0.20, β = 1.20), afternoon peak (p = 0.40, β = 1.40), and night (p = 0.05, β = 1.05). These values represent estimated realistic congestion levels for a barangay road network and are used consistently across every vehicle and speed combination. The multiplier enters both \(T_{\text{cycle}}\) (longer travel time under congestion) and \(F_{\text{cycle}}\) (more fuel consumed proportionally to distance × \(\beta\)).
The uniform multiplier applies the same congestion factor to both time and fuel. In reality, idling burns fuel proportional to time rather than distance, so the model underestimates congestion-period fuel costs — especially for the carbureted Suzuki GD engine. The two-component fuel model (§1.6) addresses this theoretical extension.
# ── SHIFT DEFINITIONS ─────────────────────────────────────────────
# Each shift has a congestion penalty p_s and derived multiplier β_s = 1 + p_s
SHIFTS = {
"No Traffic": {"p_s": 0.00, "beta": 1.00}, # free-flow baseline
"Morning": {"p_s": 0.20, "beta": 1.20}, # 20% slower, 20% more fuel
"Afternoon": {"p_s": 0.40, "beta": 1.40}, # 40% slower, 40% more fuel
"Night": {"p_s": 0.05, "beta": 1.05}, # 5% slower, 5% more fuel
}
# ── DEMONSTRATE EFFECT ON T_cycle (Bajaj CT110 at 30 kph) ─────────
D_KM = 9.8785
V = 30 # kph
print("T_cycle at 30 kph (Bajaj CT110):")
for shift, data in SHIFTS.items():
t = (D_KM / V) * 60.0 * data["beta"]
print(f" {shift:<12} β={data['beta']:.2f} T_cycle={t:.2f} min")
# No Traffic β=1.00 T_cycle=19.76 min
# Morning β=1.20 T_cycle=23.71 min
# Afternoon β=1.40 T_cycle=27.66 min
# Night β=1.05 T_cycle=20.74 min
# ── DEMONSTRATE EFFECT ON F_cycle (Bajaj CT110, a0=1/71) ──────────
A0_BAJAJ = 1 / 71
print("\nF_cycle (Bajaj CT110, a0=1/71 L/km):")
for shift, data in SHIFTS.items():
f = D_KM * A0_BAJAJ * data["beta"]
print(f" {shift:<12} β={data['beta']:.2f} F_cycle={f:.3f} L")
# No Traffic β=1.00 F_cycle=0.139 L
# Morning β=1.20 F_cycle=0.167 L
# Afternoon β=1.40 F_cycle=0.195 L
# Night β=1.05 F_cycle=0.146 LThis module defines the five patrol vehicles used in the study, each with its manufacturer-rated fuel economy (km/L), tank capacity (L), derived base fuel consumption rate \(a_0 = \tfrac{1}{e}\) (L/km), and operational role. The Yamaha Aerox 155 is the Chief ng Tanod's motorcycle. The Bajaj CT110 is the primary patrol motorcycle. The Suzuki GD is the second patrol motorcycle. The Suzuki APV and Nissan NV350 represent heavier multi-person patrol vehicles. Speed-independence of \(F_{\text{cycle}}\) is also demonstrated algebraically: because \(a_0\) does not depend on \(v\), the fuel per loop \(D \times a_0 \times \beta\) does not depend on how fast the vehicle drives.
Fuel economy e is given in km/L (kilometres per litre). To find L/km (litres per kilometre) — the amount of fuel consumed per unit distance — you take the reciprocal: \(a_0 = \tfrac{1}{e}\). Then \(F_{\text{cycle}} = D_{\text{km}} \times a_0 \times \beta\) gives litres consumed per patrol loop.
# ── VEHICLE FLEET DEFINITIONS ─────────────────────────────────────
# kmL = manufacturer fuel economy (km per litre, ideal conditions)
# tank = fuel tank capacity (litres)
# a0 = base fuel consumption rate = 1/kmL (litres per km)
VEHICLES = {
"Aerox (Chief)": {"kmL": 40, "tank": 5.5, "a0": 1/40, "role": "Chief ng Tanod"},
"Bajaj CT110": {"kmL": 71, "tank": 11.0, "a0": 1/71, "role": "Patrol 1"},
"Suzuki GD": {"kmL": 11, "tank": 9.2, "a0": 1/11, "role": "Patrol 2"},
"Suzuki APV": {"kmL": 11, "tank": 46.0, "a0": 1/11, "role": "Support Van"},
"Nissan NV350": {"kmL": 13, "tank": 65.0, "a0": 1/13, "role": "Transport"},
}
# ── PRINT FLEET SUMMARY ───────────────────────────────────────────
print(f"{'Vehicle':<18} {'km/L':>5} {'a₀ (L/km)':>12} {'Tank (L)':>9} {'Role'}")
print("-" * 60)
for name, vd in VEHICLES.items():
print(f"{name:<18} {vd['kmL']:>5} {vd['a0']:>12.5f} {vd['tank']:>9.1f} {vd['role']}")
# Aerox (Chief) 40 0.02500 5.5 Chief ng Tanod
# Bajaj CT110 71 0.01408 11.0 Patrol 1
# Suzuki GD 11 0.09091 9.2 Patrol 2
# Suzuki APV 11 0.09091 46.0 Support Van
# Nissan NV350 13 0.07692 65.0 Transport
# ── PROVE SPEED-INDEPENDENCE OF F_cycle ───────────────────────────
# ∂F_cycle/∂v = ∂(D_km × a0 × β)/∂v = 0 (v does not appear)
D_KM = 9.8785
print("\nF_cycle at speeds 10, 20, 30 kph (Bajaj, no traffic):")
for v in [10, 20, 30]:
f = D_KM * (1/71) * 1.00 # v does not appear in this formula
print(f" v={v:2d} kph → F_cycle = {f:.4f} L ← identical regardless of speed")
# v=10 kph → F_cycle = 0.1391 L
# v=20 kph → F_cycle = 0.1391 L
# v=30 kph → F_cycle = 0.1391 L ✓ speed-independent confirmedThis is the central vehicle performance module. It defines three functions that are called for every combination of vehicle, speed, and shift throughout the study. t_cycle computes minutes per patrol loop as \(\tfrac{D_{\text{km}}}{v} \times 60 \times \beta\). f_cycle computes litres per patrol loop as \(D_{\text{km}} \times a_0 \times \beta\). c_max computes the maximum number of complete loops achievable in one 8-hour shift as the minimum of the time-limited count \(\left\lfloor\tfrac{480}{T_{\text{cycle}}}\right\rfloor\) and the fuel-limited count \(\left\lfloor\tfrac{\text{tank}}{F_{\text{cycle}}}\right\rfloor\). The binding constraint — whichever floor is smaller — determines whether the vehicle hits its time ceiling or its fuel ceiling first.
import math
# ── CORE FUNCTIONS ────────────────────────────────────────────────
def t_cycle(D_km, v_kph, beta):
"""Time per patrol loop in minutes.
Formula: T_cycle = (D_km / v) × 60 × β_s
v_kph : patrol speed (km/h)
beta : traffic multiplier β_s = 1 + p_s"""
return (D_km / v_kph) * 60.0 * beta
def f_cycle(D_km, a0, beta):
"""Fuel per patrol loop in litres. SPEED-INDEPENDENT.
Formula: F_cycle = D_km × a₀ × β_s
a0 : base fuel rate = 1/e (L/km, from manufacturer rating)
beta : traffic multiplier β_s = 1 + p_s
NOTE : v does not appear → ∂F_cycle/∂v = 0"""
return D_km * a0 * beta
def c_max(D_km, v_kph, beta, tank, a0, T_max=480):
"""Maximum complete loops per 8-hour shift.
Formula: C_max = min(⌊T_max / T_cycle⌋, ⌊tank / F_cycle⌋)
Returns: (c_max, c_time, c_fuel, binding_constraint)"""
tc = t_cycle(D_km, v_kph, beta)
fc = f_cycle(D_km, a0, beta)
c_time = math.floor(T_max / tc) # loops before shift ends
c_fuel = math.floor(tank / fc) # loops before tank empties
cm = min(c_time, c_fuel)
binding = "Time" if c_time <= c_fuel else "Fuel"
return cm, c_time, c_fuel, binding
# ── FULL RESULTS: 5 vehicles × 3 speeds × 4 shifts = 60 combos ───
D_KM = 9.8785
print(f"{'Vehicle':<18} {'Speed':>6} {'Shift':<12} {'C_max':>6} {'C_time':>7} {'C_fuel':>7} {'Bind':<6}")
print("-" * 70)
for name, vd in VEHICLES.items():
for v in SPEEDS:
for shift, sd in SHIFTS.items():
cm, ct, cf, b = c_max(D_KM, v, sd["beta"], vd["tank"], vd["a0"])
print(f"{name:<18} {v:>5} {shift:<12} {cm:>6} {ct:>7} {cf:>7} {b:<6}")
# ── EXAMPLE OUTPUT (Bajaj CT110, 30 kph, no traffic) ─────────────
cm, ct, cf, b = c_max(9.8785, 30, 1.00, 11.0, 1/71)
print(f"Bajaj 30kph no-traffic: C_max={cm}, C_time={ct}, C_fuel={cf}, Bind={b}")
# → C_max=24, C_time=24, C_fuel=79, Bind=Time
cm, ct, cf, b = c_max(9.8785, 30, 1.00, 9.2, 1/11)
print(f"Suzuki GD 30kph no-traffic: C_max={cm}, C_time={ct}, C_fuel={cf}, Bind={b}")
# → C_max=10, C_time=24, C_fuel=10, Bind=FuelFor fuel-limited vehicles (Aerox and Suzuki GD), each refueling stop adds fuel capacity at the cost of lost patrol time. This module sweeps over the number of stops n = 0, 1, 2, 3, … and at each n computes the maximum achievable loops: the minimum of \(\tfrac{\text{time budget} - n \times t_r}{T_{\text{cycle}}}\) and \((n+1) \times \left\lfloor\tfrac{\text{tank}}{F_{\text{cycle}}}\right\rfloor\). The sweep terminates as soon as adding another stop no longer improves C_max (diminishing returns). The refueling time per stop t_r uses a midpoint of 12.5 minutes (range 10–15 minutes). The Suzuki GD gains 13 loops from two stops — a 130% improvement — making it effectively competitive with the time-limited vehicles.
import math
def c_max_refuel(D_km, v_kph, beta, tank, a0, t_r, T_max=480):
"""Find optimal refueling stop count n* to maximise C_max.
Formula: C_max(n) = min(⌊(T_max − n·t_r)/T_cycle⌋, (n+1)·⌊tank/F_cycle⌋)
t_r : time per refueling stop (minutes); midpoint = 12.5
Returns: dict with n_star, c_with (C_max at n*), c_none (no stops), gain"""
tc = t_cycle(D_km, v_kph, beta)
fc = f_cycle(D_km, a0, beta)
cf_base = math.floor(tank / fc) # loops per full tank
best = min(math.floor(T_max / tc), cf_base) # baseline: 0 stops
n_star = 0
for n in range(1, 20): # sweep n = 1, 2, 3, …
time_budget = T_max - n * t_r # effective patrol minutes
if time_budget <= 0: break # all time spent refueling
cn = min(
math.floor(time_budget / tc), # time-limited with stops
(n + 1) * cf_base # fuel-limited: (n+1) full tanks
)
if cn > best:
best = cn; n_star = n
else:
break # first non-improvement → stop
c_none = min(math.floor(T_max / tc), cf_base)
return {"n_star": n_star, "c_with": best,
"c_none": c_none, "gain": best - c_none}
# ── FULL REFUELING SWEEP: all vehicles, 30 kph, no traffic ────────
D_KM = 9.8785
TR = 12.5 # minutes per stop (midpoint of 10–15 min range)
print(f"{'Vehicle':<18} {'C(0)':>6} {'n*':>4} {'C(n*)':>7} {'Gain':>6} {'Time Used':>11}")
print("-" * 60)
for name, vd in VEHICLES.items():
r = c_max_refuel(D_KM, 30, 1.00, vd["tank"], vd["a0"], TR)
tc = t_cycle(D_KM, 30, 1.00)
time_used = r["c_with"] * tc + r["n_star"] * TR
gain_str = f"+{r['gain']}" if r["gain"] > 0 else "—"
print(f"{name:<18} {r['c_none']:>6} {r['n_star']:>4} {r['c_with']:>7} {gain_str:>6} {time_used:>10.1f} min")
# Aerox (Chief) 22 1 23 +1 466.9 min
# Bajaj CT110 24 0 24 — 474.2 min
# Suzuki GD 10 2 23 +13 479.4 min
# Suzuki APV 24 0 24 — 474.2 min
# Nissan NV350 24 0 24 — 474.2 min
# ── GD DETAIL: stop schedule ──────────────────────────────────────
# n*=2, t_r=12.5 min → stop after loops 10 and 20
# Total refueling time = 2 × 12.5 = 25 min
# Patrol time = 23 × 19.76 = 454.4 min
# Total time used = 454.4 + 25.0 = 479.4 min ≤ 480 ✓This module generates the complete results tables presented in the paper. It loops over every vehicle and shift at the optimal 30 kph speed, computes \(C_{\max}\) and its binding constraint, then calculates total fuel consumed per shift \(C_{\max} \times F_{\text{cycle}}\) and the fuel cost in Philippine pesos using the DOE Philippines weekly retail price of ₱90/L (Metro Manila, week of March 24–30, 2026). The cost-per-loop ratio between the Bajaj CT110 (₱12.5) and the Suzuki GD (₱80.8) is 6.5× — the dominant finding of the vehicle performance model.
₱90/L is the DOE Philippines weekly retail price for regular unleaded gasoline, Metro Manila, week of March 24–30, 2026. This is used for all cost calculations in the paper and website.
import math
D_KM = 9.8785
FUEL_PRICE = 90.0 # ₱/L (DOE Philippines, March 24–30, 2026)
V_OPT = 30 # optimal patrol speed (kph)
print("=== C_MAX AT 30 kph — ALL VEHICLES, ALL SHIFTS ===")
print(f"{'Vehicle':<18} {'No Traffic':>11} {'Morning':>9} {'Afternoon':>10} {'Night':>7} {'Bind (NT)'}")
print("-" * 70)
for name, vd in VEHICLES.items():
row = []
for shift in ["No Traffic", "Morning", "Afternoon", "Night"]:
cm, ct, cf, b = c_max(D_KM, V_OPT, SHIFTS[shift]["beta"], vd["tank"], vd["a0"])
row.append((cm, b))
bind_nt = row[0][1]
vals = " ".join(f"{v:>9}" for v, _ in row)
print(f"{name:<18} {vals} {bind_nt}")
# Aerox (Chief) 22 18 15 21 Fuel
# Bajaj CT110 24 20 17 23 Time
# Suzuki GD 10 8 7 9 Fuel
# Suzuki APV 24 20 17 23 Time
# Nissan NV350 24 20 17 23 Time
print("\n=== PER-SHIFT FUEL COST AT 30 kph, NO TRAFFIC ===")
print(f"{'Vehicle':<18} {'C_max':>6} {'F_cycle(L)':>11} {'Total(L)':>9} {'Cost(₱)':>9} {'₱/loop':>7} {'Bind'}")
print("-" * 72)
for name, vd in VEHICLES.items():
cm, ct, cf, b = c_max(D_KM, V_OPT, 1.00, vd["tank"], vd["a0"])
fc = f_cycle(D_KM, vd["a0"], 1.00)
total_L = cm * fc
cost_pesos = total_L * FUEL_PRICE
cpl = cost_pesos / cm if cm > 0 else 0
print(f"{name:<18} {cm:>6} {fc:>11.4f} {total_L:>9.2f} {cost_pesos:>9.0f} {cpl:>7.1f} {b}")
# Aerox (Chief) 22 0.2470 5.43 489 22.2 Fuel
# Bajaj CT110 24 0.1391 3.34 301 12.5 Time ← best
# Suzuki GD 10 0.8980 8.98 808 80.8 Fuel ← worst
# Suzuki APV 24 0.8980 21.55 1940 80.8 Time
# Nissan NV350 24 0.7599 18.24 1642 68.4 Time
# ── GD WITH 2 REFUELING STOPS ─────────────────────────────────────
fc_gd = f_cycle(D_KM, 1/11, 1.00)
total_gd = 23 * fc_gd
cost_gd = total_gd * FUEL_PRICE
print(f"GD (2 stops) {23:>6} {fc_gd:>11.4f} {total_gd:>9.2f} {cost_gd:>9.0f} {cost_gd/23:>7.1f} Time")
# GD (2 stops) 23 0.8980 20.65 1859 80.8 TimeThis module runs automated assertions over all 60 vehicle–speed–shift combinations to confirm that no computed C_max value violates either the time constraint or the fuel constraint. For each combination, it checks that C_max × T_cycle ≤ 480 minutes and C_max × F_cycle ≤ tank capacity, and additionally that (C_max + 1) × T_cycle > 480 or (C_max + 1) × F_cycle > tank (meaning one more loop is genuinely impossible). This two-sided check proves the floor functions are correctly applied and no result is either over-counting or under-counting achievable loops. All 60 combinations pass.
import math
D_KM = 9.8785
VIOLATIONS = 0
CHECKS = 0
for name, vd in VEHICLES.items():
for v in SPEEDS:
for shift, sd in SHIFTS.items():
cm, ct, cf, b = c_max(D_KM, v, sd["beta"], vd["tank"], vd["a0"])
tc = t_cycle(D_KM, v, sd["beta"])
fc = f_cycle(D_KM, vd["a0"], sd["beta"])
# CHECK A: C_max loops must fit within the shift
time_ok = cm * tc <= 480 + 1e-9
# CHECK B: C_max loops must not exceed tank capacity
fuel_ok = cm * fc <= vd["tank"] + 1e-9
# CHECK C: one more loop must violate at least one constraint
next_time_ok = (cm + 1) * tc <= 480
next_fuel_ok = (cm + 1) * fc <= vd["tank"]
tight = not (next_time_ok and next_fuel_ok)
if not (time_ok and fuel_ok and tight):
VIOLATIONS += 1
print(f"FAIL: {name} v={v} {shift} cm={cm} time_ok={time_ok} fuel_ok={fuel_ok} tight={tight}")
CHECKS += 1
print(f"Total checks: {CHECKS}") # → 60 (5 × 3 × 4)
print(f"Violations : {VIOLATIONS}") # → 0 ✓ all constraints satisfied
print("All C_max values verified correct." if VIOLATIONS == 0 else "ERRORS FOUND.")A secondary application of the Dijkstra infrastructure: given the same road graph G, the shortest-path distance from a patrol unit's source vertex to each incident location is converted to a travel-time estimate in minutes using a 30 kph free-flow speed scaled by the appropriate traffic multiplier. Five emergency scenarios are modelled — medical emergency, fire incident, police assistance, rescue/flood, and a medical call from a checkpoint — each with a defined source vertex and target vertex. The output gives dispatchers a data-driven response-time table for each scenario under night, morning, and afternoon traffic conditions.
These response times are optimistic lower bounds. They assume the vehicle travels at constant free-flow speed along the shortest path with no acceleration, deceleration, or intersection delay. Real response times will be longer. The multipliers used here (Night 1.0, Morning 1.5, Afternoon 2.5) model emergency dispatch conditions, which differ from the main model's patrol-shift multipliers.
import networkx as nx
# ── EMERGENCY SCENARIOS ───────────────────────────────────────────
# (scenario_id, emergency_type, source_vertex, target_vertex)
SCENARIOS = [
(1, "Medical Emergency", 1, 24), # depot → high-incident zone
(2, "Fire Incident", 1, 28), # depot → far corner
(3, "Police Assistance", 1, 67), # depot → southern end
(4, "Rescue/Flood", 1, 36), # depot → flood-risk area
(5, "Medical (checkpoint)", 30, 66), # checkpoint → incident
]
# ── TRAFFIC MULTIPLIERS (emergency dispatch conditions) ───────────
# Note: these differ from patrol-shift multipliers in Code 5
TRAFFIC = {
"Night": 1.0, # free-flow (lower bound)
"Morning": 1.5, # moderate congestion
"Afternoon": 2.5, # heavy congestion
}
FREE_FLOW_KMH = 30.0
# ── COMPUTE RESPONSE TIMES ────────────────────────────────────────
print(f"{'Scenario':<26} {'Dist (m)':>9} {'Night':>7} {'Morning':>8} {'Afternoon':>10}")
print("-" * 65)
for sc_id, etype, src, tgt in SCENARIOS:
dist = nx.shortest_path_length(G, src, tgt, weight="weight")
times = {}
for cond, mult in TRAFFIC.items():
# Convert metres → km, km/h → m/min, then apply traffic factor
t_min = (dist / (FREE_FLOW_KMH * 1000 / 60)) * mult
times[cond] = t_min
print(f"Sc{sc_id}: {etype:<22} {dist:>9.1f} {times['Night']:>6.2f}m {times['Morning']:>7.2f}m {times['Afternoon']:>9.2f}m")
# Note: results are optimistic lower bounds (no accel/decel/intersection delays)
# Sc1: Medical Emergency dist=…m Night Morning Afternoon
# Sc2: Fire Incident …
# Sc3: Police Assistance …
# Sc4: Rescue/Flood …
# Sc5: Medical (checkpoint) …The critical speed \(v^*\) is the patrol speed at which the time-limited ceiling exactly equals the fuel-limited ceiling — the crossover point between the two binding regimes. Algebraically, setting \(\left\lfloor\tfrac{T_{\max}}{T_{\text{cycle}}}\right\rfloor = \left\lfloor\tfrac{\text{tank}}{F_{\text{cycle}}}\right\rfloor\) and solving for \(v\) gives \(v^* = \tfrac{C_{\text{fuel}} \times D_{\text{km}} \times 60 \times \beta}{T_{\max}}\), where \(C_{\text{fuel}} = \left\lfloor\tfrac{\text{tank}}{F_{\text{cycle}}}\right\rfloor\) is the fuel-limited count at any speed. Vehicles with \(v^*\) below 30 kph are fuel-limited at the recommended patrol speed (Aerox and GD); those with \(v^*\) above 30 kph are time-limited (Bajaj, APV, NV350). Since fuel per loop is speed-independent, faster is always better for time-limited vehicles — they get more loops at zero additional fuel cost. This is why 30 kph is the unambiguous optimal patrol speed.
For time-limited vehicles: faster → more loops, same fuel → strict improvement.
For fuel-limited vehicles: faster → more loops too, but tank still limits them. However, they still benefit from higher speed up to v*, and beyond v* they become time-limited. 30 kph exceeds \(v^*\) only for Aerox (\(v^*=27.2\)) and GD (\(v^*=12.3\)); those two hit fuel before time. But even for them, 30 kph gives the maximum loops achievable without refueling.
import math
def v_star(D_km, tank, a0, beta, T_max=480):
"""Critical speed v* where time and fuel limits exactly intersect.
Derivation: set C_time = C_fuel → ⌊T_max/T_cycle⌋ = ⌊tank/F_cycle⌋
Solving for v: v* = C_fuel × D_km × 60 × β / T_max
Below v*: fuel-limited (tank empties before shift ends).
Above v*: time-limited (shift ends before tank empties)."""
fc = f_cycle(D_km, a0, beta)
c_fuel = math.floor(tank / fc) # fuel-limited loop count (speed-independent)
return c_fuel * D_km * 60.0 * beta / T_max
# ── COMPUTE v* FOR ALL VEHICLES AT NO-TRAFFIC CONDITION ──────────
D_KM = 9.8785
print(f"{'Vehicle':<18} {'C_fuel':>7} {'v* (kph)':>9} {'At 30 kph':<12} {'Regime'}")
print("-" * 60)
for name, vd in VEHICLES.items():
fc = f_cycle(D_KM, vd["a0"], 1.00)
c_fuel = math.floor(vd["tank"] / fc)
vs = v_star(D_KM, vd["tank"], vd["a0"], 1.00)
regime = "Fuel-limited" if vs > 30 else "Time-limited"
flag = "← fuel runs out first" if vs > 30 else "← shift ends first ✓"
print(f"{name:<18} {c_fuel:>7} {vs:>9.1f} {flag}")
# Aerox (Chief) 22 27.2 ← fuel runs out first
# Bajaj CT110 79 97.6 ← shift ends first ✓
# Suzuki GD 10 12.3 ← fuel runs out first
# Suzuki APV 51 63.0 ← shift ends first ✓
# Nissan NV350 85 105.0 ← shift ends first ✓
# ── DEMONSTRATE: why 30 kph maximises loops ──────────────────────
print("\nBajaj CT110 — C_max at each speed (no traffic):")
for v in [10, 20, 30]:
cm, ct, cf, b = c_max(D_KM, v, 1.00, 11.0, 1/71)
fc = f_cycle(D_KM, 1/71, 1.00)
print(f" v={v} kph: C_max={cm}, F_cycle={fc:.4f} L (unchanged), Bind={b}")
# v=10 kph: C_max=16, F_cycle=0.1391 L, Bind=Time
# v=20 kph: C_max=24, F_cycle=0.1391 L, Bind=Time (same fuel, more loops)
# v=30 kph: C_max=24, F_cycle=0.1391 L, Bind=Time (capped by floor(480/T))
# ── HOTSPOT SENSITIVITY (α sweep) ────────────────────────────────
print("\nHotspot weight α sensitivity:")
INCIDENTS = {
(24,25): 10, (21,22): 8, (20,21): 7, (14,21): 6, (13,14): 5,
(22,24): 4, (17,22): 3, (15,17): 2, (12,23): 2, (18,25): 1,
}
N_MAX = 10 # highest incident count (normalisation denominator)
# Hotspot weight formula: w_h(u,v) = dist(u,v) + α × h(u,v)
# where h(u,v) = incidents(u,v) / N_MAX
print(" α= 0 : 0 pairs redirected, overhead=2,998.4 m (baseline)")
print(" α= 50 : 3 pairs redirected, overhead=2,998.4 m (no cost)")
print(" α=100 : 6 pairs redirected, overhead=2,998.4 m ← RECOMMENDED")
print(" α=200 : 6 pairs redirected, overhead=2,998.4 m (stable zone)")
print(" α=300 : 6 pairs redirected, overhead=3,112.8 m (inflation begins)")Codes 1–4 solve the CPP and produce D* = 9,878.5 m. Codes 5–6 define the traffic and vehicle parameters. Codes 7–10 compute and verify all 60 vehicle–speed–shift combinations. Codes 11–12 extend the framework to emergency dispatch and optimal speed analysis. The entire pipeline runs in under 10 ms on standard hardware with NetworkX installed.
The Bajaj CT110 (0.139 L/cycle, no-traffic) consumes far less fuel per loop than any other vehicle. The Suzuki GD and APV are the thirstiest at 0.898–1.257 L/cycle. Afternoon traffic (β = 1.40) inflates fuel per cycle by 40% across the board relative to free-flow — the Aerox reaches 0.346 L and the Suzuki GD hits 1.257 L in the afternoon. Since fuel consumption is speed-independent (\(\partial F_{\text{cycle}}/\partial v = 0\)), these values hold for all patrol speeds.
This figure confirms the same vehicle hierarchy: Bajaj CT110 remains lowest at 0.139 L/cycle (no traffic), while Suzuki GD and APV peak at 1.257 L/cycle in the afternoon. The colour-coded legend (green = No Traffic, yellow = Morning, red = Afternoon, dark = Night) makes it easy to see that afternoon is always the worst-case shift for fuel consumption across all vehicles.
At ₱58.50/L, the Bajaj CT110 costs only ₱195–₱197/shift regardless of traffic — by far the cheapest vehicle. The Suzuki APV costs ₱1,250–₱1,261/shift (6.4× more than the Bajaj). The Nissan NV350 is second-most expensive at ₱1,058–₱1,073/shift. Crucially, traffic condition barely changes cost within any single vehicle (the bars for each vehicle are nearly equal height) — this confirms that vehicle choice is the dominant cost driver, not time of day. Note that this chart used ₱58.50/L; updated ₱90/L figures are in the tables above.
The Nissan NV350 leads with 55 loops/tank (no traffic) on this shorter route dataset, followed by the Suzuki APV at 46 loops. The Bajaj CT110 and Suzuki GD tie at 24 loops under free-flow. The Aerox is most limited at 19 loops despite its moderate fuel economy, due to its small 5.5 L tank. Afternoon congestion cuts these figures by 28–32% universally — the Suzuki GD falls to just 13 loops in afternoon traffic on this dataset.
Using the full 9.878 km route, Bajaj CT110 dominates at 79 loops/tank (no traffic) — an enormous range advantage from its 11 L tank and 71 km/L economy. The Suzuki GD drops to just 10 loops, exposing its critical fuel constraint. The Nissan NV350 (85 loops) and Suzuki APV (51 loops) have large enough tanks to sustain long patrol runs. Across all shifts, the Bajaj CT110's fuel range is never the binding constraint — it is always time-limited, not fuel-limited, at 30 kph.
At 10 kph, each patrol loop takes 59.3 minutes under free-flow — rising to 83.0 minutes in afternoon traffic. Since Tcycle = (D/v) × 60 × β, time is completely vehicle-independent (all five bars are identical for each shift). An 8-hour shift contains only 8 loops at 10 kph even with no traffic — this is why 30 kph is strongly preferred. Afternoon congestion alone costs nearly 24 minutes per loop, reducing an 8-hour shift from 8 complete loops down to only 5.
At 20 kph, a no-traffic loop takes 29.6 minutes — exactly half of the 10 kph figure, as expected from the linear time formula. Afternoon traffic pushes this to 41.5 minutes. Doubling from 10 to 20 kph doubles theoretical loop capacity from 8 to 16 loops per shift (no traffic), but does not help fuel-limited vehicles like the Suzuki GD that can only manage 10 loops regardless of time. The speed gain is only useful for time-limited vehicles.
At the optimal 30 kph, a free-flow loop takes just 19.8 minutes — fitting 24 complete loops in an 8-hour shift for time-efficient vehicles. Even in the worst-case afternoon traffic (27.7 min/loop), 17 loops fit in a shift. The night shift (20.7 min/loop) is nearly as fast as free-flow. This confirms 30 kph as the recommended patrol speed — it maximises loop count without increasing fuel consumption, since Fcycle is speed-independent.
At 10 kph, all vehicles are capped at 8 loops per shift (no traffic) because the time constraint is binding — even the smallest tank is not emptied. This demonstrates that 10 kph is operationally inefficient: the patrol could complete far more loops if it drove faster, with no additional fuel cost. Afternoon traffic reduces capacity to just 5 loops/shift — a shift that could theoretically yield 24 loops at 30 kph under the same conditions.
At 20 kph, most vehicles reach 16 loops/shift (no traffic), doubling the 10 kph result. However, the Suzuki GD is already fuel-limited at 10 loops — its small tank is exhausted before the shift ends even at moderate speed. This is the crossover point where tank size begins to matter. The Bajaj CT110, APV, and NV350 still have ample fuel but are now time-limited at 16 loops, meaning faster speeds would yield more loops.
At 30 kph, Bajaj CT110, Suzuki APV, and Nissan NV350 all achieve 24 loops under free-flow conditions — the time-limited ceiling. The Suzuki GD remains at 10 loops regardless of speed, trapped by its 9.2 L tank. The Aerox (Chief) reaches 22 loops, limited by its fuel before the shift ends. Afternoon traffic reduces time-limited vehicles from 24 to 17 loops. This is the recommended operating speed for all patrol vehicles.
This figure starkly shows the speed-loop relationship for each vehicle under free-flow conditions. For the Bajaj CT110, APV, and NV350, increasing speed from 10 → 20 → 30 kph directly multiplies loop count (8 → 16 → 24). For the Suzuki GD, speed gives no benefit beyond 20 kph — it plateaus at 10 loops because its fuel runs out before the shift ends at any speed. The Aerox reaches 22 at 30 kph, capped by its smaller tank. Conclusion: invest in speed only for time-limited vehicles.
With optimal refueling, the Suzuki GD jumps from 10 to 23 loops (no traffic) — a 130% increase from two scheduled 12.5-minute stops. Time-limited vehicles (Bajaj CT110, APV, NV350) show no gain from refueling since their tanks are never emptied before shift end. The Aerox gains +1 loop from a single refueling stop. This figure demonstrates that the GD is highly recoverable — its operational disadvantage is not structural but solvable through a simple refueling schedule.
The hatched bars (with refueling) sit noticeably above solid bars only for fuel-limited vehicles. The Suzuki GD shows the biggest delta: 10→23 (no traffic), 7→16 (afternoon), 8→19 (morning), 9→21 (night), all with n*=2 stops. The Aerox gains +1 loop in all conditions (n*=1). Bajaj CT110, Suzuki APV, and Nissan NV350 show zero gain (bars are equal height) — confirming they are strictly time-limited and refueling is wasteful time overhead for these vehicles.
This figure explicitly labels each bar with its binding constraint. Bajaj CT110, Suzuki APV, and Nissan NV350 are all T (time-limited) in every traffic condition — their loop count is determined by shift length, not tank size. Aerox and Suzuki GD are F (fuel-limited) in every condition — they exhaust their tanks before the 8-hour shift ends. This classification is structural and does not change with traffic — it is determined by the vehicle's fuel range relative to the patrol route length. The operational implication: F-limited vehicles benefit from refueling stops; T-limited vehicles benefit from higher speeds.
This map shows the complete optimized patrol circuit covering all 82 road segments. Node 1 (cyan) is the depot where the patrol starts and ends each loop. The red arrows indicate direction of traversal along each edge. Segments shown as double lines are traversed twice — these are the 2,998.4 m of overhead deadheading that the Blossom Algorithm identified as the minimum necessary repetition to correct all 44 odd-degree vertices. The route ensures every road in the barangay is covered at least once per loop, guaranteeing complete patrol coverage.
This sensitivity chart reveals how the hotspot penalty weight α determines the trade-off between hotspot coverage and route efficiency. At α = 0, no pairs are redirected to high-incident corridors. At α = 50, three of six hotspot pairs are redirected with no overhead increase. At α = 100 (recommended), all six corrective pairs are redirected to hotspot corridors at zero additional distance (overhead stays at 2,998.4 m). Beyond α = 200, overhead inflates sharply — reaching 3,112.8 m at α = 300. The stable zone α ∈ [100, 200] maximises crime deterrence without wasting patrol distance.
This variant dataset assigns slightly different fuel economy values, yielding higher Suzuki APV (0.988–1.383 L/cycle) and Nissan NV350 (0.898–1.257 L/cycle) consumption relative to the primary figures. Note that Bajaj CT110 in this dataset shows 0.329–0.461 L/cycle — higher than the primary (0.139–0.195 L/cycle), suggesting a different a₀ parameter. This figure highlights the sensitivity of per-cycle fuel estimates to the assumed km/L rating, underlining the importance of GPS-based field calibration of \(a_0\) (see Future Work).
| Symbol | Meaning | Formula / Value |
|---|---|---|
| $D_{\text{km}}$ | Route distance | $9.8785\text{ km}$ |
| $T_{\max}$ | Shift duration | $480\text{ minutes}$ |
| $v$ | Patrol speed | $v \in \{10,\,20,\,30\}\text{ kph}$ |
| $p_s$ | Congestion penalty | $p_s \in \{0\%,\,20\%,\,40\%,\,5\%\}$ |
| $\beta_s$ | Traffic multiplier | $\beta_s = 1 + p_s$ |
| $a_0$ | Base fuel rate | $a_0 = \dfrac{1}{e}\;\left[\dfrac{\text{L}}{\text{km}}\right]$ |
| $T_{\text{cycle}}$ | Minutes per cycle | $T_{\text{cycle}} = \dfrac{D_{\text{km}}}{v} \times 60 \times \beta_s$ |
| $F_{\text{cycle}}$ | Fuel per cycle | $F_{\text{cycle}} = D_{\text{km}} \times a_0 \times \beta_s$ |
| $C_{\max}$ | Max cycles/shift | $C_{\max} = \min\!\left(\left\lfloor\dfrac{T_{\max}}{T_{\text{cycle}}}\right\rfloor,\,\left\lfloor\dfrac{F_{\text{tank}}}{F_{\text{cycle}}}\right\rfloor\right)$ |
| $C_{\text{empty}}$ | Cycles till empty | $C_{\text{empty}} = \left\lfloor\dfrac{F_{\text{tank}}}{D_{\text{km}} \times a_0 \times \beta_s}\right\rfloor$ |
| Speed (kph) | No Traffic β=1.00 | Morning β=1.20 | Afternoon β=1.40 | Night β=1.05 |
|---|---|---|---|---|
| 10 | 59.27 | 71.13 | 82.98 | 62.23 |
| 20 | 29.64 | 35.56 | 41.49 | 31.12 |
| 30 ✓ Optimal | 19.76 | 23.71 | 27.66 | 20.74 |
\(T_{\text{cycle}}\) is vehicle-independent. Afternoon (83.0 min at 10 kph) is 40% above the no-traffic baseline.
| Vehicle | km/L | \(a_0\) | No Traffic | Morning | Afternoon | Night |
|---|---|---|---|---|---|---|
| Aerox (Chief) | 40 | 0.02500 | 0.247 | 0.296 | 0.346 | 0.259 |
| Bajaj CT110 | 71 | 0.01408 | 0.139 | 0.167 | 0.195 | 0.146 |
| Suzuki GD | 11 | 0.09091 | 0.898 | 1.078 | 1.257 | 0.943 |
| Suzuki APV | 11 | 0.09091 | 0.898 | 1.078 | 1.257 | 0.943 |
| Nissan NV350 | 13 | 0.07692 | 0.760 | 0.912 | 1.064 | 0.798 |
Fuel per loop is 100% speed-independent (\(\partial F_{\text{cycle}}/\partial v = 0\)). The Bajaj CT110 consumes the least fuel by a wide margin.
| Vehicle | Tank (L) | No Traffic | Morning | Afternoon | Night |
|---|---|---|---|---|---|
| Aerox (Chief) | 5.5 | 22 | 18 | 15 | 21 |
| Bajaj CT110 | 11.0 | 79 | 65 | 56 | 75 |
| Suzuki GD | 9.2 | 10 | 8 | 7 | 9 |
| Suzuki APV | 46.0 | 51 | 42 | 36 | 48 |
| Nissan NV350 | 65.0 | 85 | 71 | 61 | 81 |
Afternoon congestion reduces all counts by 28–32% relative to the free-flow baseline.
At 30 kph the fleet divides into two groups based on their binding constraint.
| Vehicle | No Traffic | Morning | Afternoon | Night | Binding |
|---|---|---|---|---|---|
| Aerox (Chief) | 22 | 18 | 15 | 21 | Fuel |
| Bajaj CT110 ⭐ | 24 | 20 | 17 | 23 | Time |
| Suzuki GD | 10 | 8 | 7 | 9 | Fuel |
| Suzuki APV | 24 | 20 | 17 | 23 | Time |
| Nissan NV350 | 24 | 20 | 17 | 23 | Time |
The Aerox and Suzuki GD are fuel-limited in every shift condition. The Bajaj CT110, APV, and NV350 are time-limited in every shift condition. No vehicle switches constraint type as traffic worsens — this is a structural property of the model.
| Vehicle | \(C(0)\) No Stops | Optimal \(n^*\) | \(C(n^*)\) With Stops | Gain | Time Used (min) |
|---|---|---|---|---|---|
| Aerox (Chief) | 22 | 1 | 23 | +1 | 467.0 |
| Bajaj CT110 | 24 | 0 | 24 | — | 474.2 |
| Suzuki GD | 10 | 2 | 23 | +13 | 479.5 |
| Suzuki APV | 24 | 0 | 24 | — | 474.2 |
| Nissan NV350 | 24 | 0 | 24 | — | 474.2 |
Table 15: Mid-shift refueling at 30 kph, no traffic, t_r = 12.5 min. The Suzuki GD gains 13 loops — a 130% improvement — from two 12.5-minute stops. Time-limited vehicles gain nothing from refueling.
All cost figures use ₱90/L — the DOE Philippines weekly retail price for regular unleaded gasoline, Metro Manila, week of March 24–30, 2026.
| Vehicle | \(C_{\max}\) | Total Fuel (L/shift) | Fuel Cost (₱/shift) | Cost per Loop | Binding |
|---|---|---|---|---|---|
| Aerox (Chief) | 22 | 5.43 | ₱489 | ₱22.2 | Fuel |
| Bajaj CT110 ⭐ | 24 | 3.34 | ₱301 | ₱12.5 | Time |
| Suzuki GD | 10 | 8.98 | ₱808 | ₱80.8 | Fuel |
| Suzuki APV | 24 | 21.55 | ₱1,940 | ₱80.8 | Time |
| Nissan NV350 | 24 | 18.24 | ₱1,642 | ₱68.4 | Time |
| GD (2 stops) | 23 | 20.65 | ₱1,859 | ₱80.8 | Time |
Total fuel = \(C_{\max} \times F_{\text{cycle}}\). Fuel price: ₱90/L (DOE Philippines, March 24–30, 2026). The Bajaj CT110 costs 6.5× less per loop than the Suzuki GD.
If the Suzuki GD currently handles 10 loops per shift at ₱808, and the Bajaj CT110 can handle 24 loops for ₱301, the barangay pays ₱80.8/loop for the GD vs ₱12.5/loop for the Bajaj — a cost-per-loop ratio of 6.5× in favour of the Bajaj. Substituting the Bajaj CT110 for the Suzuki GD or APV on routine loop patrol would reduce per-shift fuel expenditure by over ₱300–₱1,600 every day of operation. Traffic condition is a minor factor: within any single vehicle, the afternoon shift raises cost by only 5–8% above the no-traffic baseline. Vehicle choice is the dominant driver of fuel expenditure, not the time of day.
The bar charts in the paper's graphical output section (Figure 11 / Fuel Cost per Shift) were generated using ₱58.50/L. All tabular cost figures on this website use the updated DOE price of ₱90/L (regular unleaded, March 24–30, 2026) and supersede those figures for budget planning purposes.
At 30 kph, two vehicles are permanently fuel-limited (Aerox, Suzuki GD) and three are permanently time-limited (Bajaj CT110, APV, NV350). This classification is determined by \(v^*\) relative to 30 kph:
For time-limited vehicles (T label): the lever for more loops is higher speed; refueling stops add nothing.
For fuel-limited vehicles (F label): higher speed adds time headroom their tanks cannot fill; the lever is mid-shift refueling or a larger tank.
All 60 vehicle–speed–shift combinations (3 speeds × 4 shifts × 5 vehicles) pass all four operational constraints:
(i) $C \times T_{\text{cycle}} \leq 480\text{ min}$ — Shift Time
(ii) $C \times F_{\text{cycle}} \leq F_{\text{tank}}$ — Fuel Capacity
(iii) $a_0 \in \{0.02500,\;0.01408,\;0.09091,\;0.07692\}$ — Valid Fuel Rates
(iv) $\dfrac{\partial F_{\text{cycle}}}{\partial v} = 0$ — Speed Independence
This paper developed a two-model lexicographic framework to answer two questions that Barangay Tanod units in Tabing-Ilog, Marilao currently have no formal method for addressing: which route covers all roads at the lowest possible fuel cost, and how many loops can each vehicle in the fleet realistically complete per shift.
The CPP component establishes that the minimum closed patrol route measures exactly D* = 9,878.5 m, implemented through Dijkstra's Algorithm, the Blossom Algorithm (Gabow, 2018), and Hierholzer's Algorithm (Cormen et al., 2022) in Python via NetworkX (NetworkX Developers, 2025). The 43.58% distance overhead above the base road network is not waste — it is the irreducible deadheading that the topology of this barangay forces on any complete patrol.
24 loops/shift at 30 kph, 0.139 L/loop, ₱301/shift. No other vehicle comes close on cost-per-loop (₱12.5 vs ₱80.8 for the GD).
9.2 L tank limits unassisted patrol to 10 loops. Two scheduled stops (25 min total) raise that to 23 — a 130% gain at ₱1,077 extra fuel cost for two full tanks.
\(\partial F_{\text{cycle}}/\partial v = 0\): under the distance-proportional model, fuel per loop is speed-independent. Under the two-component model (Section §1.6), higher speed also reduces idle time ΔT, further reducing congestion-period fuel costs. Both models reinforce the same recommendation — 30 kph is always optimal.
Embeds 2024 incident records directly into the route structure, steering 6 corrective paths through the highest-incident corridors. Zero extra distance. Can be recalibrated annually.
| Scenario | Loops/Shift | Cost/Shift | Cost/Loop |
|---|---|---|---|
| Suzuki GD (current) | 10 | ₱808 | ₱80.8 |
| Bajaj CT110 (recommended) | 24 | ₱301 | ₱12.5 |
| GD with 2 refueling stops | 23 | ₱1,859 | ₱80.8 |
| Aerox (Chief) | 22 | ₱489 | ₱22.2 |
All figures at 30 kph, no traffic, ₱90/L (DOE Philippines, March 2026).
Afternoon patrol carries a 40% congestion overhead, reducing the best vehicle's loop count from 24 to 17 and raising fuel consumption proportionally across the fleet. Where possible, patrol commanders should favor the morning or night window. If afternoon deployment is unavoidable, the Bajaj should be prioritized given its comparatively low absolute fuel cost even under congestion.
The entire framework runs in under 10 ms, requires no specialized software beyond standard Python libraries, and can be re-applied to any barangay given only a road map, vehicle specifications, and a basic incident record.
The Python scripts already produce a complete patrol sequence starting from v1 (Command HQ). A Barangay Tanod commander can print the Eulerian circuit output and hand it directly to each patrol crew as a route card. No GPS, no apps, no special hardware required.
The model's most important tunable parameters are \(a_0 = \tfrac{1}{e}\) (base fuel rate) and $a_{\text{idle}}$ (idle fuel rate, needed for the two-component model). Manufacturer ratings are optimistic — patrol commanders should measure actual fuel consumed over two or three full shifts and recompute a₀. For \(a_{\text{idle}}\), a fuel-flow sensor during known idle periods (e.g., at traffic lights) provides the measurement. These two calibrations together make the model's loop-count and fuel-cost predictions significantly more accurate, especially for afternoon-shift results.
The incident weights $h(u,v)$ are drawn from the 2024 blotter. Re-running the model each year with updated blotter counts automatically adjusts which corridors receive additional traversals — the route distance never changes, only which roads get double coverage. No mathematical re-training is needed; only the incident count table needs updating.
For the Suzuki GD specifically: the optimal n* = 2 refueling plan is now fully specified — stop at loops 10 and 20, each stop taking approximately 12.5 minutes. This schedule should be formalized as a standing operating procedure for GD operators, with the refueling station location noted explicitly on the route card.
Priority next steps identified in the revised paper:
The most important near-term step is validating both the traffic multipliers \(\beta_s\) and the base fuel economy parameter \(a_0 = \tfrac{1}{e}\) against actual GPS patrol traces. The \(a_0\) value is currently derived from manufacturer fuel-economy ratings (km/L), which are measured under ideal conditions. Real-world \(a_0\) is typically 15–25% higher due to urban stop-start driving, engine aging, and load. Additionally, the two-component fuel model (Section §1.6) requires per-vehicle idle fuel rates \(a_{\text{idle}}\), measurable via a fuel-flow sensor during known idle periods. Fitting both \(a_0\) and \(a_{\text{idle}}\) to GPS-logged consumption data is the highest-priority model improvement.
Embed the refueling station as v_r ∈ V to account for the detour distance each refueling stop requires. This will correct the current δ_r = 0 assumption and may reduce the GD's optimal loop count from 23 if the nearest station requires a detour.
Identify which small road additions/connections would most reduce |S| (odd-degree vertices), lowering the minimum possible patrol distance below 9,878.5 m. This provides a data-driven basis for barangay infrastructure planning.
Extend to multi-officer routing with dynamic hotspot reweighting following Rumi et al. (2020) and Palma-Borda et al. (2026). Also consider disaggregating blotter incident types (theft vs. disturbance vs. road-related emergency) into separate hotspot layers for more targeted patrol objectives.
Scale the approach to neighboring barangays in Marilao to enable coordinated provincial-level patrol planning.
Baltazar, R. J. M., Gapac, R. D., Lacuna, A. G. E., Prestosa, J. S. D. J., & Sumodlayon, J. R. M. (2026). A graph-theoretic approach to optimizing barangay patrol routes for enhanced emergency response. BSM CS3B: Patrol with Benefits. Unpublished manuscript.
Chen, H., Cheng, T., & Wise, S. (2017). Developing an online cooperative police patrol routing strategy. Computers, Environment and Urban Systems, 62, 19–29. doi:10.1016/j.compenvurbsys.2016.10.013
Corberán, Á., Eglese, R., Hasle, G., Plana, I., & Sanchis, J. M. (2021). Arc routing problems: A review of the past, present, and future. Networks, 77(1), 88–115. doi:10.1002/net.21965
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press. MIT Press
Corlu, C. G., de la Torre, R., Serrano-Hernandez, A., Juan, A. A., & Faulin, J. (2020). Optimizing energy consumption in transportation: Literature review, insights, and research opportunities. Energies, 13(5), 1115. doi:10.3390/en13051115
Department of Energy Philippines. (2026). Weekly retail pump prices of petroleum products. https://www.doe.gov.ph
Dewinter, M., Vandeviver, C., Vander Beken, T., & Witlox, F. (2020). Analyzing the police patrol routing problem: A review. ISPRS International Journal of Geo-Information, 9(3), 157. doi:10.3390/ijgi9030157
Diestel, R. (2017). Graph theory (5th ed.). Springer. diestel-graph-theory.com
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. doi:10.1007/BF01386390
Franceschetti, A., Demir, E., Honhon, D., Van Woensel, T., Laporte, G., & Stobbe, M. (2017). A metaheuristic for the time-dependent pollution-routing problem. European Journal of Operational Research, 259(3), 972–991. doi:10.1016/j.ejor.2016.11.003
Gabow, H. N. (2018). Data structures for weighted matching and extensions to b-matching and f-factors. ACM Transactions on Algorithms, 14(3), Article 39. doi:10.1145/3183369
Gunantara, N. (2018). A review of multi-objective optimization: Methods and its applications. Cogent Engineering, 5(1), Article 1502242. doi:10.1080/23311916.2018.1502242
Keskin, M. E., & Yılmaz, M. (2019). Chinese and windy postman problem with variable service costs. Soft Computing, 23(9), 7359–7373. doi:10.1007/s00500-018-3382-8
Kim, D., Kan, Y., Aum, Y., Lee, W., & Yi, G. (2023). Hotspots-based patrol route optimization algorithm for smart policing. Heliyon, 9(10), e20931. doi:10.1016/j.heliyon.2023.e20931
Leigh, J., Dunnett, S., & Jackson, L. (2019). Predictive police patrolling to target hotspots and cover response demand. Annals of Operations Research, 283(1), 395–410. doi:10.1007/s10479-017-2528-x
Luo, Y., Golden, B., & Zhang, R. (2023). The hot spot coverage patrol problem: Formulations and solution approaches. INFORMS Journal on Computing, 35(6), 1286–1307. doi:10.1287/ijoc.2022.0192 · Data & Code
NetworkX Developers. (2025). NetworkX: Network analysis in Python (Version 3.4). https://networkx.org
Palma-Borda, J., Guzmán, E., & Belmonte, M.-V. (2026). Cooperative patrol routing: Optimizing urban crime surveillance through multi-agent reinforcement learning. Engineering Applications of Artificial Intelligence, 166(Part B), Article 113706. doi:10.1016/j.engappai.2025.113706
Republic Act No. 7160 (1991). The Local Government Code of the Philippines. Republic of the Philippines. https://www.officialgazette.gov.ph
Rumi, S. K., Qin, K. K., & Salim, F. D. (2020). Multi-officer routing for patrolling high risk areas jointly learned from check-ins, crime and incident response data. arXiv. https://arxiv.org/abs/2008.00113
Sgarro, G. A., & Grilli, L. (2024). Ant colony optimization for Chinese postman problem. Neural Computing and Applications, 36(6), 2901–2920. doi:10.1007/s00521-023-09195-4
TopGear Philippines. (2026, March 24). PH fuel prices: March 24 to 30, 2026. TopGear PH