寻求Node.js/NPM/Google API实现配送APP非往返最优路径方案

Hey there! Building a delivery app with optimal routing? Awesome—let's break down two practical solutions for your Node.js setup, whether you want the reliability of Google's APIs (great for real-world traffic-aware routes) or a self-hosted open-source approach (perfect for keeping costs down).

Google's Routes API handles heavy lifting like real-time traffic, road restrictions, and automatic waypoint optimization—ideal for production-grade delivery apps where accuracy matters most. Since you don't need to return to the starting point, the API will optimize the order of your delivery stops to minimize total travel time/distance.

Step-by-Step Setup: #

1. Enable the API: Create a Google Cloud project, enable the Routes API, and generate an API key (keep this secure!).
2. Install the official client:

   npm install @googlemaps/client-routes
   

3. Code Example:

   const { RoutesClient } = require("@googlemaps/client-routes");
   
   // Initialize client with your API key
   const routesClient = new RoutesClient({ key: "YOUR_GOOGLE_API_KEY" });
   
   async function computeOptimalDeliveryRoute() {
     const routeRequest = {
       origin: {
         location: { latLng: { latitude: 37.7749, longitude: -122.4194 } } // Your starting point
       },
       // Note: We don't set a fixed final destination—instead, use waypoints for all stops
       waypoints: [
         { location: { latLng: { latitude: 37.7895, longitude: -122.401 } }, stopover: true },
         { location: { latLng: { latitude: 37.7580, longitude: -122.405 } }, stopover: true },
         { location: { latLng: { latitude: 37.7652, longitude: -122.410 } }, stopover: true }
       ],
       travelMode: "DRIVE",
       routingPreference: "TRAFFIC_AWARE_OPTIMAL", // Prioritize real-time traffic
       routeModifiers: { avoidTolls: false, avoidHighways: false },
       languageCode: "en-US",
       units: "METRIC"
     };
   
     try {
       const [response] = await routesClient.computeRoutes(routeRequest);
       console.log("✅ Optimal Delivery Route Order:");
       response.route.legs.forEach((leg, idx) => {
         const start = leg.startLocation.latLng;
         const end = leg.endLocation.latLng;
         console.log(`${idx + 1}. ${start.latitude.toFixed(4)}, ${start.longitude.toFixed(4)} → ${end.latitude.toFixed(4)}, ${end.longitude.toFixed(4)}`);
         console.log(`   Distance: ${leg.distance.text} | Duration: ${leg.duration.text}\n`);
       });
     } catch (err) {
       console.error("❌ Error calculating route:", err.message);
     }
   }
   
   computeOptimalDeliveryRoute();
   

Key Notes: #

• The API automatically reorders waypoints to find the fastest path—no manual TSP solving needed.
• Check Google's pricing page for quota limits and costs (there's a free tier for small-scale testing).

If you prefer to avoid third-party API dependencies, combine a TSP (Traveling Salesman Problem) solver with the Google Distance Matrix API (to get real-world travel times) or use open-source routing engines like OSRM. Here's a lightweight approach using tsp-solver and Google's Distance Matrix:

Step-by-Step Setup: #

1. Install dependencies:

   npm install tsp-solver @google/maps
   

2. Code Example:

   const googleMaps = require("@google/maps");
   const tspSolver = require("tsp-solver");
   
   // Initialize Google Maps client
   const gmapsClient = googleMaps.createClient({
     key: "YOUR_GOOGLE_API_KEY",
     Promise: Promise
   });
   
   // Define your locations: index 0 = starting point, rest = delivery stops
   const deliveryLocations = [
     { lat: 37.7749, lng: -122.4194 }, // Start
     { lat: 37.7895, lng: -122.401 }, // Stop 1
     { lat: 37.7580, lng: -122.405 }, // Stop 2
     { lat: 37.7652, lng: -122.410 }  // Stop 3
   ];
   
   async function findOptimalRoute() {
     // Step 1: Fetch travel times between all pairs of locations
     const locationStrings = deliveryLocations.map(loc => `${loc.lat},${loc.lng}`);
     const distanceMatrix = await gmapsClient.distanceMatrix({
       origins: locationStrings,
       destinations: locationStrings,
       mode: "driving",
       traffic_model: "best_guess"
     }).asPromise();
   
     // Build a time matrix (in seconds) for the TSP solver
     const timeMatrix = distanceMatrix.json.rows.map(row => 
       row.elements.map(el => el.duration.value)
     );
   
     // Step 2: Solve TSP with greedy algorithm (fast, good for <20 stops)
     const solver = tspSolver.greedy();
     const { path } = solver(timeMatrix, { start: 0, end: null }); // end: null = don't return to start
   
     // Step 3: Print the optimal route
     console.log("✅ Optimal Delivery Order (Indices):", path);
     console.log("\n📋 Route Details:");
     for (let i = 0; i < path.length - 1; i++) {
       const from = deliveryLocations[path[i]];
       const to = deliveryLocations[path[i+1]];
       const travelTimeMins = Math.floor(timeMatrix[path[i]][path[i+1]] / 60);
       console.log(`${i+1}. (${from.lat.toFixed(4)}, ${from.lng.toFixed(4)}) → (${to.lat.toFixed(4)}, ${to.lng.toFixed(4)}) | Travel Time: ${travelTimeMins} mins`);
     }
   }
   
   findOptimalRoute();
   

Key Notes: #

• The greedy TSP solver gives a good approximate solution (fast enough for most delivery use cases). For larger numbers of stops (>20), consider using a more advanced algorithm like simulated annealing.
• If you want to cut Google API costs entirely, you can self-host OSRM (Open Source Routing Machine) to generate distance matrices locally, but it requires more setup (map data, server hosting).

内容的提问来源于stack exchange，提问作者punith bp