Best algorithm for planning a trip between two places that completes the most errands along the way?

I am given a list of errands to complete. Each errand has a duration and location. A location is open/closed depending in the time and day of the week.

On a given day, I will take a trip from an origin to a destination. The earliest departure and latest arrival times are defined by depart_after and arrive_by.

I want to plan the a route that covers as many errands as possible along the way while still arriving at my destination on time.

At a high level, how would you approach solving this problem? I am thinking Dynamic Programming, but am not sure if there is an even more efficient way.

I plan on leveraging googlemapsapi distance_matrix(locations, departure_time) which returns a matrix of travel times for a list of locations. I would like to minimize calls to this function.

Example input:

trip_info = {'day': '2023-02-28',
             'origin': 'Work', 
             'destination': 'Home',
             'depart_at': '9:30', 
             'arrive_after': '12:00'}

errands = {'Drop off dry cleaners': {'duration': "10mins",
                                     'location': "Mikes Dry Clean",
                                     'opening_close_hours': {'Mon-Fri': [('07:00', '20:00')],
                                                             'Sat': [('09:00', '18:00')]}},
           'Buy groceries': {'duration': "45mins",
                             'location': "Midtown Market",
                             'open_close_hours': {'Mon-Fri': [('07:00', '20:00')],
                                                  'Sat-Sun': [('10:00', '19:00')]}},
           'Refill gas': {'duration': "20mins",
                          'location': "Springfield Costco",
                          'open_close_hours': {'Mon-Wed': [('07:00', '20:00')],
                                               'Fri': [('09:00', '18:00')]}}}

Sample output:

best_route=(
    {'location': "Work", 'errand': None, 'arrive': None, 'depart': '10:00'},
    {'location': "Springfield Costco", 'errand': 'Refill gas', 'arrive': '10:23', 'depart': '10:43'},
    {'location': "Midtown Market", 'errand': 'Buy groceries', 'arrive': '11:00', 'depart': '11:45'},
    {'location': "Home", 'errand': None, 'arrive': '12:00', 'depart': None}
)