Wolfram Language (Mathematica), 153*95 bytes, 14535

Nest[Flatten[Join[#,{Max@#+1},#]&/@Partition[#,Max@#+1,1]]//.{b__,a__,a__,c__}:>{b,a,c}&,{0},4]

Try it online!

CJam (6 * 240 = 1440)

5e!72>

Online demo, validation (outputs the index at which each permutation of 0..4 can be found; it needs to flatten the output because the original program gives suitable output to stdout but what it places on the stack is not directly usable).

Approach stolen from Sanchises, although the permutation order of CJam is different, giving a different substring.

CJam (22 * 207 = 4554)

0a4{)W@+W+1$)ewa*W-}/

Online demo, validation.

Dissection

This uses a simple recursive construction.

0a       e# Start with a superpermutation of one element, [0]
4{       e# for x = 0 to 3:
  )      e#   increment it: n = x+1
  W@+W+  e#   wrap the smaller superpermutation in [-1 ... -1]
  1$)ew  e#   split into chunks of length n+1
  a*    e#   insert an n between each chunk
  W-     e#   remove the -1s from the ends
}/

MATL, 16 x 442 = 7072

4Y25:Y@!)K442&:)

Try it online!

MATL port of my Octave answer. -442 thanks to Luis Mendo

Charcoal, 29 bytes, output length 153, score 4437

”)⊞⧴�r3⁼Ｈ⁴↓¦σ✳ＬïpＷＳ [Ｔ↑ZωÞ”‖Ｏ

Try it online! Link is to verbose version of code. Explanation: Like @TFeld, I just print half of a superpermutation and mirror it. I calculated the superpermutation using the following code:

Push(u, w);
for (u) {
    Assign(Plus(Plus(i, Length(i)), i), h);
    Assign(Ternary(i, Join(Split(w, i), h), h), w);
    Assign(Incremented(Length(i)), z);
    if (Less(z, 5)) for (z) Push(u, Slice(h, k, Plus(k, z));
}
Print(w);

This translates to a 45-byte program in Charcoal so would have scored 6885.

Octave, 27 x 442 = 11934

'01234'(perms(1:5)'(4:445))

Try it online!

So, it turns out, naively generating all the permutations and then truncating to the shortest substring that is still a valid superpermutation is shorter than generating the shortest superpermutation. Sadly, this time the score is not a palindrome.

Octave, 97 x 153 = 14841

a=sym(9);while i<120
i=0;a+=1;q='01234';for t=q(perms(1:5))'
i+=any(regexp(char(a),t'));end
end
a

Try it online!

Entry updated for a few things

• a++ is not implemented for symbolic numbers.
• contains() is not implemented in Octave. Replaced with any(regexp()).
• In the online link, I manually entered an a very close to the 153-length superpermutation. This allows for the solution to be verified.

Japt -P, 2376 (11 x 216)

4o ¬á Ë+4+D

Try it!

-1 byte thanks to @ Shaggy!

Port of Anders Kaseorg's Pyth answer.

JavaScript (ES6), 26975 (325 * 83 bytes)

With this scoring system, there's little room for something between 'hardcode the optimal supermutation' and 'just use a short built-in to concatenate all permutations', at least in non-esolangs.

Here's an attempt anyway.

f=(a=[0,1,2,3,4],p=r='')=>a.map((v,i)=>f(a.filter(_=>i--),p+v))|~r.search(p)?r:r+=p

Try it online!

It generates a string of 325 bytes:

012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210

Brachylog, score = 2907 (19 bytes × 153)

4⟦pᶠP∧~l.g;Pz{sᵈ}ᵐ∧

Too slow to see anything, but if you change 4 by 2 you can test it: Try it online!

This finds the shortest superpermutation as such:

4⟦                   The range [0,1,2,3,4]
  pᶠP                P is the list of all permutations of this range
     ∧
      ~l.            Try increasing lengths for the output
         g;Pz        Zip the output with P
             {sᵈ}ᵐ   For each permutation, it must be a substring of the output
                  ∧

05AB1E, score = 1673 (7 bytes · 239)

žBœ∊{3ý

Try it online!

How it works

žB          push 1024
  œ         permutations: ["1024", "1042", …, "4201"]
   ∊        vertically mirror: ["1024", "1042", …, "4201", "4201", …, "1042", "1024"]
    {       sort: ["0124", "0124", "0142", "0142", …, "4210", "4210"]
     3      push 3
      ý     join: "01243012430142301423…3421034210"

Pyth, score = 1944 (9 bytes · 216)

s+R+4d.p4

Try it online!

How it works

 +R   .p4   append to each permutation d of [0, 1, 2, 3]:
   +4d        [4] + d
s           concatenate

Jelly, 3000 (600*5 bytes)

5ḶŒ!F

Try it online!

Perl 6, 7191 (153*47 bytes)

say first *.comb(permutations(5).all.join),0..*

Try it online!

Finds the first number that contains all permutations of the digits 0 to 4. This will take a long time to execute, but you can test it with the first two permutations 0 and 0,1

05AB1E, score: 5355 2160 (216 * 10 bytes)

3ÝœJε4yJ}J

Port of @AndersKaseorg's Pyth answer, so make sure to upvote him!

Try it online.

Explanation:

3Ý           # Push a list in the range [0,3]: [0,1,2,3]
  œ          # Get all possible permutations of this list
   J         # Join each inner list together to a single string
    ε        # Map each string `y` to:
             #  (Push string `y` implicitly)
     4       #  Push 4
      y      #  Push string `y` again
       J     #  Join all three together
        }J   # After the map: Join all strings together to a single string
             # (and output it implicitly as result)

Python 2, Score: 24327 15147 12852 12628 (154*82 bytes)

S=str(int('OH97GKT83A0GJRVO309F4SGSRWD0S2T292S1JBPVKJ6CRUY8O',36))
print S+S[::-1]

Try it online!

Also:

Python 2, 12628 (154*82 bytes)

S=oct(int('FS02C3XQJX14OTVMGM70CGCPWU41MNJZ0CO37ZMU0A0Y',36))[:-1]
print S+S[::-1]

Try it online!