refining initial solution for OneDepot

cvvergara · cvvergara · commit fd1456a77e4d · 2019-07-01T11:31:53.000-05:00
diff --git a/include/vrp/vehicle.h b/include/vrp/vehicle.h
@@ -344,8 +344,10 @@ class Vehicle : public Identifier, public PD_problem {
 
 
      std::pair<POS, POS> position_limits(const Vehicle_node node) const;
+     std::pair<POS, POS> drop_position_limits(const Vehicle_node node) const;
 
  private:
+     POS getDropPosLowLimit(const Vehicle_node &node) const;
      POS getPosLowLimit(const Vehicle_node &node) const;
      POS getPosHighLimit(const Vehicle_node &node) const;
 };
diff --git a/include/vrp/vehicle_pickDeliver.h b/include/vrp/vehicle_pickDeliver.h
@@ -162,7 +162,7 @@ class Vehicle_pickDeliver : public Vehicle {
       * Can generate time window violation
       * No capacity violation
       */
-     void semiLIFO(const Order &order);
+     bool semiLIFO(const Order &order);
 
 #if 0
      void insert_while_compatibleJ(
diff --git a/sql/vrp_basic/_pgr_vrpOneDepot.sql b/sql/vrp_basic/_pgr_vrpOneDepot.sql
@@ -90,7 +90,7 @@ BEGIN
             $$' || orders_sql || '$$,
             $$' || trucks_sql || '$$,
             $$' || $3 || '$$,
-            max_cycles := 1,
+            max_cycles := 0,
             initial_sol := 7 ); ';
 
     RAISE DEBUG '%', orders_sql;
diff --git a/src/pickDeliver/fleet.cpp b/src/pickDeliver/fleet.cpp
@@ -77,8 +77,10 @@ Fleet::release_truck(size_t id) {
 
 Vehicle_pickDeliver
 Fleet::get_truck(size_t order) {
+#if 0
     msg.log << "Available vehicles: " << un_used << "\n";
     msg.log << "NOT Available vehicles: " << used << "\n";
+#endif
     auto idx = un_used.front();
 
     for (const auto i : un_used) {
@@ -155,7 +157,9 @@ Fleet::add_vehicle(
                     vehicle.capacity,
                     vehicle.speed,
                     factor));
+#if 0
         msg.log << "inserting vehicle: " << m_trucks.back().tau() << "\n";
+#endif
         pgassert((m_trucks.back().idx() + 1)  == m_trucks.size());
         pgassert(m_trucks.back().is_ok());
     }
diff --git a/src/pickDeliver/optimize.cpp b/src/pickDeliver/optimize.cpp
@@ -117,6 +117,7 @@ Optimize::inter_swap() {
 #endif
         }
     }
+    pgassert(false);
     while (!p_swaps.empty()) {
         swapped_f = swap_order() || swapped_f;
     }
@@ -188,18 +189,13 @@ Optimize::swap_worse(Vehicle_pickDeliver &to, Vehicle_pickDeliver &from) {
             /*
              * insert them in the other truck
              */
-#if 1
             if (this->get_kind() == OneDepot) {
-                pgassert(false);
-                from_truck.insert(to_order);
-                to_truck.insert(from_order);
+                from_truck.semiLIFO(to_order);
+                to_truck.semiLIFO(from_order);
             } else {
-#endif
                 from_truck.insert(to_order);
                 to_truck.insert(from_order);
-#if 1
             }
-#endif
 
             if (from_truck.is_feasable() && to_truck.is_feasable()) {
                 /*
@@ -228,9 +224,9 @@ Optimize::swap_worse(Vehicle_pickDeliver &to, Vehicle_pickDeliver &from) {
 #endif
                     msg.log
                         << "\n Found Swap order "
-                        << from_order.pickup().id()
+                        << from_order
                         << " from truck " << from_truck.idx()
-                        << " with order " << to_order.pickup().id()
+                        << " with order " << to_order
                         << " of truck " << to_truck.idx();
 
                     swapped = true;
diff --git a/src/pickDeliver/pickDeliver.c b/src/pickDeliver/pickDeliver.c
@@ -93,6 +93,7 @@ process(
     PGR_DBG("total vehicles %ld", total_vehicles);
 
 
+#if 0
     for (size_t i = 0; i < total_pd_orders; i++) {
         PGR_DBG("%ld %f pick %f %f %ld - "
                 "%f %f %f deliver %f %f %ld - %f %f %f ",
@@ -138,7 +139,7 @@ process(
 
                vehicles_arr[i].cant_v);
     }
-
+#endif
     PGR_DBG("load matrix");
     Matrix_cell_t *matrix_cells_arr = NULL;
     size_t total_cells = 0;
diff --git a/src/pickDeliver/vehicle.cpp b/src/pickDeliver/vehicle.cpp
@@ -391,6 +391,45 @@ Vehicle::position_limits(const Vehicle_node node) const {
     return std::make_pair(low, high);
 }
 
+std::pair<size_t, size_t>
+Vehicle::drop_position_limits(const Vehicle_node node) const {
+    POS high = getPosHighLimit(node);
+    POS low = getDropPosLowLimit(node);
+    return std::make_pair(low, high);
+}
+
+/*
+ * start searching from postition low = pos(E)
+ *
+ * S 1 2 3 4 5 6 7 ..... E
+ * node -> E
+ * node -> ...
+ * node -> 7
+ * node -> 6
+ * node -> 5
+ * node /-> 4
+ *
+ * return low_limit = 5
+ *
+ */
+size_t
+Vehicle::getDropPosLowLimit(const Vehicle_node &nodeI) const {
+    invariant();
+
+    POS low = 0;
+    POS high = m_path.size();
+    POS low_limit = high;
+
+    /* J == m_path[low_limit - 1] */
+    while (low_limit > low
+            && m_path[low_limit - 1].is_compatible_IJ(nodeI, speed())
+            && !m_path[low_limit - 1].is_pickup()) {
+        --low_limit;
+    }
+
+    invariant();
+    return low_limit;
+}
 
 /*
  * start searching from postition low = pos(E)
diff --git a/src/pickDeliver/vehicle_pickDeliver.cpp b/src/pickDeliver/vehicle_pickDeliver.cpp
@@ -87,10 +87,14 @@ Vehicle_pickDeliver::Vehicle_pickDeliver(
         double factor) :
     Vehicle(id, kind, starting_site, ending_site, p_capacity, p_speed, factor),
     cost((std::numeric_limits<double>::max)()) {
+#if 0
         ENTERING();
+#endif
         m_orders_in_vehicle.clear();
         invariant();
+#if 0
         EXITING();
+#endif
     }
 
 
@@ -264,6 +268,7 @@ Vehicle_pickDeliver::do_while_feasable(
     msg.log << "m_feasable_orders" << m_feasable_orders << "\n";
 #endif
     auto current_feasable = m_feasable_orders * unassigned;
+    bool inserted = false;
 
     while (!current_feasable.empty()) {
 #if 0
@@ -298,8 +303,7 @@ Vehicle_pickDeliver::do_while_feasable(
                 insert(order);
                 break;
             case OneDepot:
-                order = m_orders[m_orders.find_best_I(current_feasable)];
-                semiLIFO(order);
+                inserted = semiLIFO(order);
                 break;
             default: pgassert(false);
         }
@@ -310,7 +314,7 @@ Vehicle_pickDeliver::do_while_feasable(
 
         if (!is_feasable()) {
             erase(order);
-        } else {
+        } else if ((kind != OneDepot) || (kind == OneDepot && inserted)) {
             assigned += order.idx();
             unassigned -= order.idx();
             if (kind == BestBack) {
@@ -417,123 +421,75 @@ Vehicle_pickDeliver::is_order_feasable(const Order &order) const {
     return test_truck.is_feasable();
 }
 
-void
+bool
 Vehicle_pickDeliver::semiLIFO(const Order &order) {
-    ENTERING();
     invariant();
     pgassert(!has_order(order));
 
-    auto pick_pos(position_limits(order.pickup()));
-    pgassert(pick_pos.first == 1);
-    pick_pos.second = 1;
-    auto deliver_pos(position_limits(order.delivery()));
-#if 1
-    std::ostringstream err_log;
-    msg.log << "\n\tpickup limits (low, high) = ("
-        << pick_pos.first << ", "
-        << pick_pos.second << ") "
-        << "\n\tdeliver limits (low, high) = ("
-        << deliver_pos.first << ", "
-        << deliver_pos.second << ") "
-        << "\noriginal" << tau();
-#endif
+    /*
+     * Insert pick up as first picked
+     */
+    Vehicle::insert(1, order.pickup());
 
-    if (pick_pos.second < pick_pos.first) {
-        /* pickup generates twv evrywhere,
-         *  so put the order as last */
-        push_back(order);
-        return;
-    }
+    auto deliver_pos(drop_position_limits(order.delivery()));
 
-    if (deliver_pos.second < deliver_pos.first) {
-        /* delivery generates twv evrywhere,
-         *  so put the order as last */
-        push_back(order);
-        return;
-    }
     /*
-     * Because delivery positions were estimated without
-     * the pickup:
-     *   - increase the upper limit position estimation
+     * delivery generates twv in all positions
      */
-    ++deliver_pos.second;
+    if (deliver_pos.second < deliver_pos.first) {
+        /*
+         * Remove inserted pickup
+         */
+        Vehicle::erase(1);
+        invariant();
+        return false;
+    }
 
+    pgassert(!has_order(order));
+
+    while (deliver_pos.first <= deliver_pos.second) {
+        Vehicle::insert(deliver_pos.second, order.delivery());
+
+        if (is_feasable() && !m_path[deliver_pos.second + 1].is_pickup()) {
+            /*
+             * Found a position to insert the delivery
+             */
 
-    auto d_pos_backup(deliver_pos);
-    auto best_pick_pos = m_path.size();
-    auto best_deliver_pos = m_path.size() + 1;
-    auto current_duration(duration());
-    auto min_delta_duration = (std::numeric_limits<double>::max)();
-    auto found(false);
-    pgassertwm(!has_order(order), err_log.str());
-    while (pick_pos.first <= pick_pos.second) {
-#ifndef NDEBUG
-        err_log << "\n\tpickup cycle limits (low, high) = ("
-            << pick_pos.first << ", "
-            << pick_pos.second << ") ";
-#endif
-        Vehicle::insert(pick_pos.first, order.pickup());
-#ifndef NDEBUG
-        err_log << "\npickup inserted: " << tau();
-#endif
 
-        while (deliver_pos.first <= deliver_pos.second) {
-            Vehicle::insert(deliver_pos.first, order.delivery());
             m_orders_in_vehicle += order.idx();
-            pgassertwm(has_order(order), err_log.str());
-#ifndef NDEBUG
-            err_log << "\ndelivery inserted: " << tau();
-#endif
-            if (is_feasable()) {
-                pgassert(is_feasable());
-                auto delta_duration = duration() - current_duration;
-                if (delta_duration < min_delta_duration) {
-#ifndef NDEBUG
-                    err_log << "\nsuccess" << tau();
-#endif
-                    min_delta_duration = delta_duration;
-                    best_pick_pos = pick_pos.first;
-                    best_deliver_pos = deliver_pos.first;
-                    found = true;
-                }
-            }
-            Vehicle::erase(deliver_pos.first);
-#ifndef NDEBUG
-            err_log << "\ndelivery erased: " << tau();
-#endif
-            ++deliver_pos.first;
+
+            /*
+             * There is one more order in the vehicle
+             */
+            pgassert(has_order(order));
+            pgassert(is_feasable());
+            pgassert(!has_cv());
+            pgassert(!has_twv());
+            pgassert(has_order(order));
+            invariant();
+            return true;
+
         }
-        Vehicle::erase(pick_pos.first);
-#ifndef NDEBUG
-        err_log << "\npickup erased: " << tau();
-#endif
-        m_orders_in_vehicle -= order.idx();
-        pgassertwm(!has_order(order), err_log.str());
 
-        deliver_pos = d_pos_backup;
-#ifndef NDEBUG
-        err_log << "\n\trestoring deliver limits (low, high) = ("
-            << deliver_pos.first << ", "
-            << deliver_pos.second << ") ";
-#endif
-        ++pick_pos.first;
-    }
-    pgassertwm(!has_order(order), err_log.str());
-    if (!found) {
-        /* order causes twv
-         *  so put the order as last */
-        push_back(order);
-        return;
+        /*
+         * This position in path is not suitable
+         */
+        Vehicle::erase(deliver_pos.second);
+
+        /*
+         * got to next position
+         */
+        --deliver_pos.second;
     }
-    Vehicle::insert(best_pick_pos, order.pickup());
-    Vehicle::insert(best_deliver_pos, order.delivery());
 
-    m_orders_in_vehicle += order.idx();
-    pgassertwm(is_feasable(), err_log.str());
-    pgassertwm(has_order(order), err_log.str());
-    pgassertwm(!has_cv(), err_log.str());
+    /*
+     * Order could not be inserted
+     */
+    Vehicle::erase(1);
+
+    pgassert(!has_order(order));
     invariant();
-    EXITING();
+    return false;
 }
 
 }  //  namespace vrp
diff --git a/test/vrp_basic/test.conf b/test/vrp_basic/test.conf
@@ -5,10 +5,9 @@
         'comment' => 'VRP Single depot test for any versions.',
         'data' => ['../../tools/testers/vrpOneDepot.data'],
         'tests' => [qw(
-            doc-pgr_vrpOneDepot
+            oneDepotWrapper
             )],
         'nottested' => [qw(
-            oneDepotWrapper
             )],
         'documentation' => [qw(
             doc-pgr_vrpOneDepot
