2
$\begingroup$

I am testing Montoya et al. 2017 dataset and trying to replicate the Result from this paper The electric vehicle routing problem with capacitated charging stations. I am unable to replicate the exact Result.

EDIT:: Read me file:

Montoya et al. 2016
Instances for the electric vehicle routing problemw with non-linear charging functions
Number of instances: 120
-------------------------------------------------------------------------------------------------------------
<network>
- the node with type=0 is the depot
- the nodes with type=1 are the customers
- the nodes with type=2 are the charging stations (CSs)
- coordinates are given in km
- nodes with type=2 define the type of charging station (slow, normal, fast) in tag <cs_type>
- computations must be done using double precision (14 decimal) Euclidean distances
<fleet>
- There is just one type of electric vehicle in the 120 instances
- Routes start and end at node 0 (the depot)
- <speed_factor> is given in km/h
- <consumption_rate> defines the energy consumption in wh/km
- <battery_capacity> defines the total capacity in wh
- <function cs_type="X"> defines the charging function of the electric vehicle when charged at a station of type X
- The charging functions are piecewise linear functions with 3 break points (pus point 0,0)
- The break points are given in 2D coordinates (X:<charging_time>,Y:<battery_level>)
- <battery_level> is given in wh
- <charging_time> is given in h
<requests>
- Each customer has 1 request
- Each customer has a service time

Instances are named using the following convention: tcAcBsCcDE, where:
- A is the method used to place the customers (i.e., 0: random uniform, 1: clustered, 2: mixture of both)
- B is the number of customers
- C is the number of the CSs, 
- D is 't' if the CSs are located using a p-median heuristic and 'f' if the CSs were randomly located
- E is the number of the instance for each combination of parameters (i.e., E={0,1,2,3,4}).

For example here - tc0c10s2ct1:

<?xml version="1.0" encoding="UTF-8"?>
<instance>
  <info>
    <dataset>Montoya et al. 2016</dataset>
    <name>tc0c10s2ct1</name>
  </info>
  <network>
    <nodes>
      <node id="0" type="0">
        <cx>77.59</cx>
        <cy>78.35</cy>
      </node>
      <node id="1" type="1">
        <cx>12.44</cx>
        <cy>47.61</cy>
      </node>
      <node id="2" type="1">
        <cx>108.2</cx>
        <cy>93.64</cy>
      </node>
      <node id="3" type="1">
        <cx>58.51</cx>
        <cy>24.22</cy>
      </node>
      <node id="4" type="1">
        <cx>116.26</cx>
        <cy>13.76</cy>
      </node>
      <node id="5" type="1">
        <cx>113.56</cx>
        <cy>85.73</cy>
      </node>
      <node id="6" type="1">
        <cx>5.09</cx>
        <cy>69.91</cy>
      </node>
      <node id="7" type="1">
        <cx>89.27</cx>
        <cy>58.94</cy>
      </node>
      <node id="8" type="1">
        <cx>78.54</cx>
        <cy>57.16</cy>
      </node>
      <node id="9" type="1">
        <cx>111.56</cx>
        <cy>51.2</cy>
      </node>
      <node id="10" type="1">
        <cx>11.05</cx>
        <cy>72.52</cy>
      </node>
      <node id="11" type="2">
        <cx>20.26</cx>
        <cy>60.26</cy>
        <custom>
          <cs_type>fast</cs_type>
        </custom>
      </node>
      <node id="12" type="2">
        <cx>70.9</cx>
        <cy>30.98</cy>
        <custom>
          <cs_type>fast</cs_type>
        </custom>
      </node>
    </nodes>
    <euclidean />
    <decimals>14</decimals>
  </network>
  <fleet>
    <vehicle_profile type="0">
      <departure_node>0</departure_node>
      <arrival_node>0</arrival_node>
      <max_travel_time>10</max_travel_time>
      <speed_factor>40</speed_factor>
      <custom>
        <consumption_rate>125</consumption_rate>
        <battery_capacity>16000</battery_capacity>
        <charging_functions>
          <function cs_type="fast">
            <breakpoint>
              <battery_level>0</battery_level>
              <charging_time>0.0</charging_time>
            </breakpoint>
            <breakpoint>
              <battery_level>13600</battery_level>
              <charging_time>0.31</charging_time>
            </breakpoint>
            <breakpoint>
              <battery_level>15200</battery_level>
              <charging_time>0.39</charging_time>
            </breakpoint>
            <breakpoint>
              <battery_level>16000</battery_level>
              <charging_time>0.51</charging_time>
            </breakpoint>
          </function>
        </charging_functions>
      </custom>
    </vehicle_profile>
  </fleet>
  <requests>
    <request id="1" node="1">
      <service_time>0.5</service_time>
    </request>
    <request id="2" node="2">
      <service_time>0.5</service_time>
    </request>
    <request id="3" node="3">
      <service_time>0.5</service_time>
    </request>
    <request id="4" node="4">
      <service_time>0.5</service_time>
    </request>
    <request id="5" node="5">
      <service_time>0.5</service_time>
    </request>
    <request id="6" node="6">
      <service_time>0.5</service_time>
    </request>
    <request id="7" node="7">
      <service_time>0.5</service_time>
    </request>
    <request id="8" node="8">
      <service_time>0.5</service_time>
    </request>
    <request id="9" node="9">
      <service_time>0.5</service_time>
    </request>
    <request id="10" node="10">
      <service_time>0.5</service_time>
    </request>
  </requests>
</instance>

My Result:

 visit   charge Left      Distance Traveled     Charge Time
    0  16000.000000000000    1.000000000000  0.000000000000
    7  13168.341640928415   23.653266872629  0.000000000000
    8  11808.761627652219   34.529906978831  0.000000000000
   11  16000.000000000000   92.892295552301  0.407119592116
   10  14083.249413069105  108.226300247712  0.000000000000
    6  13269.945003576588  114.732735523605  0.000000000000
    1  10334.939413718195  138.212780242437  0.000000000000
    3   3876.494118989694  189.880342600285  0.000000000000
   12  16000.000000000000  203.994509242359  0.461853733869
    4   9935.170550625542  252.513144837343  0.000000000000
   12  16000.000000000000  301.031780432328  0.421778989613
    9  10323.728116095881  346.441955503542  0.000000000000
    5   6000.244097101502  381.029827655526  0.000000000000
    2   4805.871222953778  390.584810648696  0.000000000000
    0    528.831870200578  424.801125470665  0.000000000000

Total time travel + charging = 11.885 + service Time(0.5*10) = 16.885, but in paper tc0c10s2ct1 - 12.30

for another example tc0c10s2cf1:

<?xml version="1.0" encoding="UTF-8"?>
<instance>
  <info>
    <dataset>Montoya et al. 2016</dataset>
    <name>tc0c10s2cf1</name>
  </info>
  <network>
    <nodes>
      <node id="0" type="0">
        <cx>77.59</cx>
        <cy>78.35</cy>
      </node>
      <node id="1" type="1">
        <cx>12.44</cx>
        <cy>47.61</cy>
      </node>
      <node id="2" type="1">
        <cx>108.2</cx>
        <cy>93.64</cy>
      </node>
      <node id="3" type="1">
        <cx>58.51</cx>
        <cy>24.22</cy>
      </node>
      <node id="4" type="1">
        <cx>116.26</cx>
        <cy>13.76</cy>
      </node>
      <node id="5" type="1">
        <cx>113.56</cx>
        <cy>85.73</cy>
      </node>
      <node id="6" type="1">
        <cx>5.09</cx>
        <cy>69.91</cy>
      </node>
      <node id="7" type="1">
        <cx>89.27</cx>
        <cy>58.94</cy>
      </node>
      <node id="8" type="1">
        <cx>78.54</cx>
        <cy>57.16</cy>
      </node>
      <node id="9" type="1">
        <cx>111.56</cx>
        <cy>51.2</cy>
      </node>
      <node id="10" type="1">
        <cx>11.05</cx>
        <cy>72.52</cy>
      </node>
      <node id="11" type="2">
        <cx>93.39</cx>
        <cy>10.8</cy>
        <custom>
          <cs_type>fast</cs_type>
        </custom>
      </node>
      <node id="12" type="2">
        <cx>8.9</cx>
        <cy>10.98</cy>
        <custom>
          <cs_type>fast</cs_type>
        </custom>
      </node>
    </nodes>
    <euclidean />
    <decimals>14</decimals>
  </network>
  <fleet>
    <vehicle_profile type="0">
      <departure_node>0</departure_node>
      <arrival_node>0</arrival_node>
      <max_travel_time>10</max_travel_time>
      <speed_factor>40</speed_factor>
      <custom>
        <consumption_rate>125</consumption_rate>
        <battery_capacity>16000</battery_capacity>
        <charging_functions>
          <function cs_type="fast">
            <breakpoint>
              <battery_level>0</battery_level>
              <charging_time>0.0</charging_time>
            </breakpoint>
            <breakpoint>
              <battery_level>13600</battery_level>
              <charging_time>0.31</charging_time>
            </breakpoint>
            <breakpoint>
              <battery_level>15200</battery_level>
              <charging_time>0.39</charging_time>
            </breakpoint>
            <breakpoint>
              <battery_level>16000</battery_level>
              <charging_time>0.51</charging_time>
            </breakpoint>
          </function>
        </charging_functions>
      </custom>
    </vehicle_profile>
  </fleet>
  <requests>
    <request id="1" node="1">
      <service_time>0.5</service_time>
    </request>
    <request id="2" node="2">
      <service_time>0.5</service_time>
    </request>
    <request id="3" node="3">
      <service_time>0.5</service_time>
    </request>
    <request id="4" node="4">
      <service_time>0.5</service_time>
    </request>
    <request id="5" node="5">
      <service_time>0.5</service_time>
    </request>
    <request id="6" node="6">
      <service_time>0.5</service_time>
    </request>
    <request id="7" node="7">
      <service_time>0.5</service_time>
    </request>
    <request id="8" node="8">
      <service_time>0.5</service_time>
    </request>
    <request id="9" node="9">
      <service_time>0.5</service_time>
    </request>
    <request id="10" node="10">
      <service_time>0.5</service_time>
    </request>
  </requests>
</instance>

My Result:

 visit   charge Left      Distance Traveled     Charge Time
    0  16000.000000000000    1.000000000000  0.000000000000
    7  13168.341640928411   23.653266872629  0.000000000000
    8  11808.761627652217   34.529906978831  0.000000000000
   12  16000.000000000000  118.090196590638  0.478915082207
    1  11399.917629813544  154.890855552163  0.000000000000
   10   8281.323695842644  179.839607023983  0.000000000000
    6   7468.019286350116  186.346042299876  0.000000000000
   12  16000.000000000000  245.399077784969  0.508030819589
    3   9581.703764821985  296.745447666384  0.000000000000
   11  16000.000000000000  334.118041903363  0.398077930861
   4  13117.405411352520  357.178798612556  0.000000000000
  11  16000.000000000000  380.239555321750  0.276706518021
   9  10462.755508152066  424.537511256523  0.000000000000
   5   6139.271489157687  459.125383408507  0.000000000000
   2   4944.898615009963  468.680366401677  0.000000000000
   0    667.859262256759  502.896681223647  0.000000000000

Total time travel + charging = 14.209 + service Time(0.5*10) = 19.209, but in paper tc0c10s2cf1 - 19.75

What is wrong with my Result?

My objective function minimizes distance traveled and charging time. (Not using an exact formulation from the paper, I am trying a simple formulation)

for charging time I am using:

f = opt_model.piecewise(0, [(0, 0), (13600, 0.31), (15200, 0.39), (16000, 0.51)], 1)

I have used simple flow and charging constraints.

$\endgroup$
  • $\begingroup$ I have noticed that even simple TSP on tc0c10s2ct1 takes times about 8-9 and on top of that 0.5*10 service time always goes greater than 12.5 that is without charging, with charging it will take more time. $\endgroup$ – anoop Apr 3 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.