Problem Background

I am working on a problem where using an A* search algorithm, I need to find the fastest route between two nodes in a graph given a specific cost function. Here is an overview of the cost function:

Package finds the fastest route, in expectation, for a certain delivery driver. Whenever this driver drives on a road with a speed limit >= 50 mph, there is a chance that a package will fall out of their truck and be destroyed. Consequently, this mistake will add an extra 2*(t_road + t_trip) hours to their trip, where t_trip is the time it took to get from the start city to the beginning of the road, and t_road is the time it takes to drive the length of the road segment.

For a road of length l miles, the probability p of this mistake happening is equal to tanh(l/1000) if the speed limit is >= 50 mph, and 0 otherwise. This means that, in expectation, it will take t_road + p * 2(t_road + t_trip) hours to drive on this road.

So, I have constructed my graph where every city in a given dataset is a node and each road that connects two cities is an edge. Each edge has dictionary of weights defined as: {'distance':int, 'speed':int, 'time':float}

Problem Overview

So, I am trying to figure out where in my A* search algorithm I am going wrong because when I try calculating the package cost function, there are some edge cases (look below for an example) where my cost function is not performing properly.

My Attempt(s)

Here is a method I wrote to calculate the package cost:

def delivery_calculation(path, G):
    result = 0

    for i in range(0, len(path)-1):
        edge = G.get_edge(path[i], path[i+1])

        if not edge:
            continue
        if edge[1]['speed'] >= 50:
            prob = math.tanh(edge[1]['distance']/1000)
        else:
            prob = 0

        t_road = edge[1]['time']
        t_trip = total_metric(path[0:i+1], G, 'time')
        result += t_road + (prob*(2*(t_road+t_trip)))

    return result

where path is a list of nodes, G is a graph, and get_edge() returns an edge and its weight between two nodes. It should be noted that the graph is undirected.

So within my A*, when I check all adjacent nodes and look to add them to the fringe (implemented as a priority queue), I calculate what the package cost would be for a given adjacent node. This, to me, seems like correct logic, but I could be wrong. Here is the code for that:

for move in G.get_adjacent(curr_node):

    neighbor = move[0]
    weight = move[1]
    path = [neighbor]
    node = curr_node

    while node is not None:
        path.append(node)
        node = tracked_nodes[node]
    path.reverse()
            
    ncost = float(delivery_calculation(path, G))

where get_adjacent() gets all nodes that are adjacent to a given node.

So ncost is then used for the priority metric within my priority queue. My thinking behind that is if I want the fastest route, the smallest package cost should lead me there.

Results

So, the problem here is that for some searches, other cost functions turn up faster routes for package costs than the package cost function itself. An example:

I want to find the fastest route between Bloomington, Indiana, and Chicago, Illinois based on time

Total hours: 3.900 (cost function)
Total hours for package delivery: 4.725

I want to find the fastest route between Bloomington, Indiana, and Chicago, Illinois based on package time

Total hours: 4.115
Total hours for package delivery: 4.736 (cost function)

I've spent hours looking at my code and trying to rework the logic, but I cannot figure out why this would happen. Potentially how the float type is working and rounding values? This is one of the only edge cases that I've found (another being Bloomington, Indiana to Buffalo, New York). A working example would look like:

I want to find the fastest route between Denver, Colorado, and Milwaukee, Wisconsin based on time

Total hours: 16.387 (cost function)
Total hours for package delivery: 33.704

I want to find the fastest route between Denver, Colorado, and Milwaukee, Wisconsin based on package time

Total hours: 21.513
Total hours for package delivery: 23.037 (cost function)

Any ideas? I am absolutely stuck. Thank you in advance and I appreciate you taking the time to read this entire post.