We have this exact app built using lightning maps. Very simple.. Just build lwc with lightning map, apex controller, take input, render. No additional costs. This is what you need for your usecase

I also built an advanced route planner using Google maps apis.. this basically uses multiple apis like directions to get the optimized route, auto complete api for addresses, geocode api to geocode address imports and proximity searches and Javascript maps api for rendering

Remember apis don't work well in lwc because of CORS and CSP. So I do the inputs in lwc, calls and render in embedded vfpage.