Traveling Pumpkin Problem
Jelly, 30 29 27 25 bytes
_AṢæ..
0,0ṭṚç2\+\&lt;S
Œ!ç€Ṁ

Try it online!
Apparently Jelly's dot product just ignores a list size mismatch and doesn't multiply the extra elements of the other array, just adds them. Shaves off 2 bytes.
Explanation
_AṢæ..              Helper link to calculate distance. Arguments: a, b
_                     subtract the vertices from each other
 A                    take absolute values of axes
  Ṣ                   sort the axes
   æ..                dot product with [0.5]

0,0ṭṚç2\+\&lt;S        Helper link to calculate max cities. Arguments: perm, max
0,0                   create pair [0,0]
   ṭ                  append that to the permutation
    Ṛ                 reverse the permutation (gets the [0,0] to the beginning)
     ç2\              find distances of each pair using the previous link
        +\            find all partial sums
          &lt;           see if each sum was less than the max
           S          sum to count cases where it was

Œ!ç€Ṁ               Main link. Arguments: cities, max
Œ!                    get permutations of cities
  ç€                  find max cities for each permutation using the previous link
    Ṁ                 take the maximum